Efficient algorithms for counting and reporting pairwise intersections between convex polygons

Prosenjit Gupta, Ravi Janardan, Michiel Smid

Research output: Contribution to journalArticlepeer-review

9 Scopus citations

Abstract

Let S be a set of convex polygons in the plane with a total of n vertices, where a polygon consists of the boundary as well as the interior. Efficient algorithms are given for counting and for reporting output-sensitively the I pairs of polygons that intersect. The algorithm for the counting problem takes O(n4/3+ε) time and the algorithm for the reporting problem takes O(n4/3+ε + I) time, where ε > 0 is an arbitrarily small constant. The result is based on an interesting characterization of the intersection of two convex polygons in terms of the intersection of certain trapezoids from their trapezoidal decomposition. The problem is interesting and challenging because the output size, I, can be much smaller than the total number of intersections between the polygons and because the number of polygons and their sizes can depend on n.

Original languageEnglish (US)
Pages (from-to)7-13
Number of pages7
JournalInformation Processing Letters
Volume69
Issue number1
DOIs
StatePublished - Jan 15 1999

Bibliographical note

Funding Information:
search was supported in part by NSF grant CCR-92-00270. Also supportedi n part by a Grant-in-Aid of Researchf rom the Graduate School of the University of Minnesota. ’ Email: pgupta@delsoft.com. Work done while at the Max-Planck-Institut ftir Informatik, Saarbrticken, Germany and at the University of Minnesota, USA. The research was su._ pportedi n part by NSF &ant CCR-9240270. 2 Email: michiel@isg.cs.uni-magdeburg.de. Part of this work was done while the author was at the Department of Computer Science, King’s College London, UK and at the Max-Plan&Institut fiir Informatik, S&bticken, Germany.

Keywords

  • Algorithms
  • Computational geometry
  • Data structures

Fingerprint Dive into the research topics of 'Efficient algorithms for counting and reporting pairwise intersections between convex polygons'. Together they form a unique fingerprint.

Cite this