Applications of a new space-partitioning technique

DOI10.1007/BF02189304zbMath0773.68065WikidataQ105462088 ScholiaQ105462088MaRDI QIDQ1196362

Pankaj K. Agarwal, Micha Sharir

Publication date: 14 December 1992

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/131231

zbMATH Keywords

spanning treesray shootinghidden surface removallow stabbing number

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items (17)

On range searching with semialgebraic sets ⋮ 3-D vertical ray shooting and 2-D point enclosure, range searching, and arc shooting amidst convex fat objects ⋮ A new asymmetric inclusion region for minimum weight triangulation ⋮ Connected component and simple polygon intersection searching ⋮ Space reduction and an extension for a hidden line elimination algorithm ⋮ On fat partitioning, fat covering and the union size of polygons ⋮ Visibility testing and counting for uncertain segments ⋮ Optimal partition trees ⋮ Simplex Range Searching and Its Variants: A Review ⋮ Spanners for geodesic graphs and visibility graphs ⋮ An incidence theorem in higher dimensions ⋮ A faster algorithm for computing motorcycle graphs ⋮ How hard is half-space range searching? ⋮ Ray shooting and stone throwing with near-linear storage ⋮ Connected component and simple polygon intersection searching ⋮ EFFICIENT NON-INTERSECTION QUERIES ON AGGREGATED GEOMETRIC DATA ⋮ Iterated snap rounding

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Thermal stresses in an elastic space with a perfectly rigid flat inclusion under perpendicular heat flow
• Fracture analysis of a penny-shaped magnetically dielectric crack in a magnetoelectroelastic material
• Range searching with efficient hierarchical cuttings
• Merging visibility maps
• A new improved energy-momentum tensor.
• Visibility and intersection problems in plane geometry
• Combinatorial complexity bounds for arrangements of curves and spheres
• Partitioning arrangements of lines. II: Applications
• Worst-case optimal insertion and deletion methods for decomposable searching problems
• Quasi-optimal upper bounds for simplex range searching and new zone theorems
• Implicitly representing arrangements of lines or segments
• An improved technique for output-sensitive hidden surface removal
• Efficient ray shooting and hidden surface removal
• Quasi-optimal range searching in spaces of finite VC-dimension
• Lines in space: Combinatorics and algorithms
• Ray Shooting and Parametric Search
• Spanning trees with low crossing number
• A linear algorithm for determining the separation of convex polyhedra
• Decomposable searching problems I. Static-to-dynamic transformation
• Ray Shooting and Other Applications of Spanning Trees with Low Stabbing Number
• Space searching for intersecting objects

This page was built for publication: Applications of a new space-partitioning technique