FINDING TAILORED PARTITIONS

被引：58

作者：

HERSHBERGER, J

SURI, S

机构：

[1] DEC SYST RES CTR,PALO ALTO,CA 94301

[2] BELL COMMUN RES INC,MORRISTOWN,NJ 07960

来源：

JOURNAL OF ALGORITHMS | 1991年 / 12卷 / 03期

关键词：

D O I：

10.1016/0196-6774(91)90013-O

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We consider the following problem: given a planar set of points S, a measure μ acting on S, and a pair of values μ1 and μ2, does there exist a bipartition S = S1 ∪ S2 satisfying μ(Si) ≤ μi for i = 1,2? We present algorithms for several natural measures, including the diameter (set measure), the area, perimeter, or diagonal of the smallest enclosing axes-parallel rectangle (rectangular measure), the side length of the smallest enclosing axes-parallel square (square measure), and the radius of the smallest enclosing circle (circular measure). The algorithms run in time O(n log n) for the set, rectangle, and square measures, and in time O(n2 log n) for the circular measure. The problem of partitioning S into an arbitrary number k of subsets is known to be NP-complete for many of these measures. © 1991.

引用

页码：431 / 463

页数：33

共 18 条

[1]

ASANO T, 1988, 4TH P ANN ACM S COMP, P252

[2] DIAMETER PARTITIONING [J].

AVIS, D .

DISCRETE & COMPUTATIONAL GEOMETRY, 1986, 1 (03) :265-276

[3] ON THE CONVEX LAYERS OF A PLANAR SET [J].

CHAZELLE, B .

IEEE TRANSACTIONS ON INFORMATION THEORY, 1985, 31 (04) :509-517

[4] THE POWER OF GEOMETRIC DUALITY [J].

CHAZELLE, B ;

GUIBAS, LJ ;

LEE, DT .

BIT, 1985, 25 (01) :76-90

[5]

DREZNER Z, 1987, NAV RES LOG, V34, P229, DOI 10.1002/1520-6750(198704)34:2<229::AID-NAV3220340207>3.0.CO

[6]

2-1

[7]

EDELSBRUNNER H, 1983, IEEE T INFORM THEORY, V29, P551, DOI 10.1109/TIT.1983.1056714

[8]

EDELSBRUNNER H, 1987, EATCS MONOGRAPHS THE, V10

[9]

Garey M.R., 1979, COMPUTERS INTRACTABI, V174

[10]

GUHA S, 1989, UNPUB ON TIME SET BI

← 1 2 →