Intersection queries in sets of disks

DOI10.1007/BF01994881zbMath0761.68098OpenAlexW2171758733MaRDI QIDQ1196457

Mark H. Overmars, Marc J. van Kreveld, Pankaj K. Agarwal

Publication date: 14 December 1992

Published in: BIT (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01994881

zbMATH Keywords

orthogonal range searchingconjugation treesintersection queriesray shooting problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Data structures (68P05)

Related Items (2)

Computing depth orders for fat objects and related problems ⋮ The forest hiding problem

Cites Work

• Unnamed Item
• Unnamed Item
• A deterministic view of random sampling and its use in geometry
• Storing line segments in partition trees
• On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles
• \(\epsilon\)-nets and simplex range queries
• Halfplanar range search in linear space and \(O(n^{0.695})\) query time
• Fractional cascading. I: A data structuring technique
• On \(k\)-sets in arrangements of curves and surfaces
• Quasi-optimal range searching in spaces of finite VC-dimension
• Optimal Point Location in a Monotone Subdivision
• Searching and storing similar lists
• Space searching for intersecting objects

This page was built for publication: Intersection queries in sets of disks