COVERING CONVEX-SETS WITH NONOVERLAPPING POLYGONS

被引：21

作者：

EDELSBRUNNER, H ^{[1
]}

ROBISON, AD ^{[1
]}

SHEN, XJ ^{[1
]}

机构：

[1] E CHINA INST TECHNOL,DEPT COMP SCI,NANJING,PEOPLES R CHINA

来源：

DISCRETE MATHEMATICS | 1990年 / 81卷 / 02期

关键词：

D O I：

10.1016/0012-365X(90)90147-A

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We prove that given n≥3 convex, compact, and pairwise disjoint sets in the plane, they may be covered with n non-overlapping convex polygons with a total of not more than 6n-9 sides, and with not more than 3n-6 distinct slopes. Furthermore, we construct sets that require 6n-9 sides and 3n-6 slopes for n≥3. The upper bound on the number of slopes implies a new bound on a recently studied transversal problem. © 1990.

引用

页码：153 / 164

页数：12