Reporting intersecting pairs of convex polytopes in two and three dimensions

DOI10.1016/S0925-7721(02)00049-4zbMath1015.52009MaRDI QIDQ1862123

Sariel Har-Peled, Mark H. Overmars, Jan Vahrenhold, Pankaj K. Agarwal, Mark T. de Berg, Micha Sharir

Publication date: 10 March 2003

Published in: Computational Geometry (Search for Journal in Brave)

zbMATH Keywords

output-sensitive algorithmsconvex polytopes

Mathematics Subject Classification ID

Three-dimensional polytopes (52B10) Computational aspects related to convexity (52B55) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Convex sets in (2) dimensions (including convex curves) (52A10)

Related Items (3)

Optimal algorithms for some polygon enclosure problems for VLSI layout analysis ⋮ Unnamed Item ⋮ Counting and representing intersections among triangles in three dimensions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Efficient algorithms for counting and reporting pairwise intersections between convex polygons
• Range searching with efficient hierarchical cuttings
• Partitioning arrangements of lines. II: Applications
• The power of geometric duality
• Fractional cascading. I: A data structuring technique
• Cutting hyperplanes for divide-and-conquer
• Algorithms for bichromatic line-segment problems and polyhedral terrains
• On range searching with semialgebraic sets
• Applications of random sampling in computational geometry. II
• A fast planar partition algorithm. I
• Algorithms for Reporting and Counting Geometric Intersections
• Red-Blue Intersection Detection Algorithms, with Applications to Motion Planning and Collision Detection
• Ray Shooting Amidst Convex Polygons in 2D
• An optimal algorithm for intersecting line segments in the plane
• Reporting red-blue intersections between two sets of connected line segments
• Online point location in planar arrangements and its applications

This page was built for publication: Reporting intersecting pairs of convex polytopes in two and three dimensions