The Mono- and Bichromatic Empty Rectangle and Square Problems in All Dimensions (Extended Abstract)

被引：19

作者：

Backer, Jonathan ^{[1
]}

Keil, J. Mark ^{[1
]}

机构：

[1] Univ Saskatchewan, Dept Comp Sci, Saskatoon, SK S7N 0W0, Canada

来源：

LATIN 2010: THEORETICAL INFORMATICS | 2010年 / 6034卷

关键词：

VORONOI DIAGRAMS; ALGORITHM;

D O I：

10.1007/978-3-642-12200-2_3

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

The maximum empty rectangle problem is as follows: Given a set of red points in R-d and an axis-aligned hyperrectangle B, find an axis-aligned hyperrectangle R of greatest volume that is contained in B and contains no red points. In addition to this problem, we also consider three natural variants: where we find a hypercube instead of a hyperrectangle, where we try to contain as many blue points as possible instead of maximising volume, and where we do both. Combining the results of this paper with previous results, we now know that all four of these problems (a) are NP-complete if d is part of the input, (b) have polynomial-time sweep-plane solutions for any fixed d >= 3, and (c) have near linear time solutions in two dimensions.

引用

页码：14 / 25

页数：12

共 20 条

[1]

Agarwal P.K., 2007, P 23 ANN S COMP GEOM, P294, DOI [10.1145/1247069.1247121, DOI 10.1145/1247069.1247121]

[2] GEOMETRIC APPLICATIONS OF A MATRIX-SEARCHING ALGORITHM [J].

AGGARWAL, A ;

KLAWE, MM ;

MORAN, S ;

SHOR, P ;

WILBER, R .

ALGORITHMICA, 1987, 2 (02) :195-208

[3]

Aggarwal A, 1987, P 3 ANN S COMP GEOM, P278, DOI DOI 10.1145/41958.41988

[4] On approximating the depth and related problems [J].

Aronov, Boris ;

Har-Peled, Sariel .

SIAM JOURNAL ON COMPUTING, 2008, 38 (03) :899-921

[5] Voronoi diagrams in higher dimensions under certain polyhedral distance functions [J].

Boissonnat, JD ;

Sharir, M ;

Tagansky, B ;

Yvinec, M .

DISCRETE & COMPUTATIONAL GEOMETRY, 1998, 19 (04) :485-519

[6] COMPUTING THE LARGEST EMPTY RECTANGLE [J].

CHAZELLE, B ;

DRYSDALE, RL ;

LEE, DT .

SIAM JOURNAL ON COMPUTING, 1986, 15 (01) :300-315

[7] An efficient algorithm for computing the maximum empty rectangle in three dimensions [J].

Datta, A ;

Soundaralakshmi, S .

INFORMATION SCIENCES, 2000, 128 (1-2) :43-65

[8] Computing the maximum bichromatic discrepancy, with applications to computer graphics and machine learning [J].

Dobkin, DP ;

Gunopulos, D ;

Maass, W .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1996, 52 (03) :453-470

[9]

DUMITRESCU A, 2009, ARXIV09093127

[10] The maximum box problem and its application to data analysis [J].

Eckstein, J ;

Hammer, PL ;

Liu, Y ;

Nediak, M ;

Simeone, B .

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS, 2002, 23 (03) :285-298

← 1 2 →