Efficient algorithms for counting and reporting pairwise intersections between convex polygons

DOI10.1016/S0020-0190(98)00187-2MaRDI QIDQ294592zbMATHOpenAlexFDO

Authors Prosenjit Gupta, Ravi Janardan, Michiel Smid

Publication date 16 June 2016

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL http://www.sciencedirect.com/science/article/pii/S0020019098001872?np=y

zbMATH Keywords

computational geometrydata structures

Mathematics Subject Classification ID

Data structures (68P05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational aspects related to convexity (52B55)

Recommendations

• Reporting intersecting pairs of convex polytopes in two and three dimensions
• Publication:4778548
• Reporting Intersections of Polygons
• A simple linear algorithm for intersecting convex polygons
• A new O(n\(\cdot \log \,n)\) algorithm for computing the intersection of convex polygons

Cites work

• scientific article; zbMATH DE number 4032498 (Why is no real title available?)
• scientific article; zbMATH DE number 49092 (Why is no real title available?)
• scientific article; zbMATH DE number 1241835 (Why is no real title available?)
• An optimal algorithm for intersecting line segments in the plane
• Efficient algorithms for counting and reporting pairwise intersections between convex polygons
• Efficient partition trees
• Quasi-optimal upper bounds for simplex range searching and new zone theorems

Cited in

(6)

• scientific article; zbMATH DE number 1830727 (Why is no real title available?)
• Reporting intersecting pairs of convex polytopes in two and three dimensions
• Algorithms for the multiple label placement problem
• Optimal algorithms for some polygon enclosure problems for VLSI layout analysis
• An algorithm for set operations on nonconvex polygons (with an application to census tracts)
• Efficient algorithms for counting and reporting pairwise intersections between convex polygons

This page was built for publication: Efficient algorithms for counting and reporting pairwise intersections between convex polygons

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q294592)