The rectangle enclosure and point-dominance problems revisited

Prosenjit Gupta, Ravi Janardan, Michiel Smid, Bhaskar Dasgupta

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 Scopus citations


We consider the problem of reporting the pairwise enclosures in a set of n axes-parallel rectangles in IR2, which is equivalent to reporting dominance pairs in a set of n points in IR4. Over a decade ago, Lee and Preparata [LP82] gave an O(n log2 n + k)-time and O(n)-space algorithm for these problems, where k is the number of reported pairs. Since that time, the question of whether there is a faster algorithm has remained an intriguing open problem. In this paper, we give an algorithm which runs in O (n log n log log n + k log log n) time and uses O(n) space. Thus, although our result is not a strict improvement over the Lee-Preparata algorithm for the full range of k, it is, nevertheless, the first result since [LP82] to make any progress on this long-standing open problem. Our algorithm is based on the divide-and-conquer paradigm. The heart of the algorithm is the solution to a red-blue dominance reporting problem (the "merge" step). We give a novel solution for this problem which is based on the iterative application of a sequence of non-trivial sweep routines. This solution technique should be of independent interest. We also present another algorithm whose bounds match the bounds given in [LP82], but which is simpler. Finally, we consider the special case where the rectangles have at most a constant number, a, of different aspect ratios, which is often the case in practice. For this problem, we give an algorithm which runs in O(αnlog n + k) time and uses O(n) space.

Original languageEnglish (US)
Title of host publicationProceedings of the 11th Annual Symposium on Computational Geometry, SCG 1995
PublisherAssociation for Computing Machinery
Number of pages10
ISBN (Electronic)0897917243
StatePublished - Sep 1 1995
Event11th Annual Symposium on Computational Geometry, SCG 1995 - Vancouver, Canada
Duration: Jun 5 1995Jun 7 1995

Publication series

NameProceedings of the Annual Symposium on Computational Geometry
VolumePart F129372


Other11th Annual Symposium on Computational Geometry, SCG 1995

Bibliographical note

Funding Information:
*Department of Computer Minnesota, Minneapolis, MN {PWPta. j anardan}@cs. umn. edu. t The research of these authors was supported in part by NSF grant CCR-92-00270. Part of this work was done while PG was visiting the Max-Planck-Institut fiir Informatik. PG thanks the MPI and the International Computer Science Institute for partial support. ‘Max-Planck-Institut fiir Informatik, D-66123 Saarbriic-ken, Germany. Email: michiel~mpi-sb mpg. de. This author was supported by the ESPRIT Basic Research Actions Program, under contract No. 7141 (project ALCOM II). $DIMACS, Rutgers University, Piscataway, NJ 08855, U.S.A. E-mail: bhaskar~dimacs. rutgers. edu.

Publisher Copyright:
© 1995 ACM.


Dive into the research topics of 'The rectangle enclosure and point-dominance problems revisited'. Together they form a unique fingerprint.

Cite this