Intersection queries in sets of disks

DOI10.1007/3-540-52846-6_107MaRDI QIDQ5056120zbMATH OpenOpenAlexFDO

Authors Marc Van Kreveld, Mark H. Overmars, Pankaj K. Agarwal

Publication date 9 December 2022

Published in SWAT 90 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-52846-6_107

Mathematics Subject Classification ID

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

Recommendations

• Intersection queries in sets of disks
• Intersection and Closest-Pair Problems for a Set of Planar Discs
• Intersection Queries in Curved Objects
• Connected component and simple polygon intersection searching
• Finding the largest disk containing a query point in logarithmic time with linear storage

Cites work

• -nets and simplex range queries
• Fractional cascading. I: A data structuring technique
• Halfplanar range search in linear space and \(O(n^{0.695})\) query time
• scientific article; zbMATH DE number 4032498 (Why is no real title available?)
• On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles
• Optimal Point Location in a Monotone Subdivision
• Quasi-optimal range searching in spaces of finite VC-dimension
• Searching and storing similar lists
• Space searching for intersecting objects
• Storing line segments in partition trees
• Visibility and intersection problems in plane geometry

Cited in

(7)

• Intersection queries in sets of disks
• Lower bounds for set intersection queries
• Finding the largest disk containing a query point in logarithmic time with linear storage
• Intersection Queries in Curved Objects
• Finding the largest disk containing a query point in logarithmic time with linear storage (extended abstract)
• On intersection searching problems involving curved objects
• Unit-disk range searching and applications

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

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