Optimal solutions for a class of point retrieval problems

DOI10.1016/S0747-7171(85)80028-6zbMath0573.68063MaRDI QIDQ1062772

Herbert Edelsbrunner, Bernard Chazelle

Publication date: 1985

Published in: Journal of Symbolic Computation (Search for Journal in Brave)

zbMATH Keywords

query pointfixed-radius neighbour problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Convex sets in (2) dimensions (including convex curves) (52A10) Information storage and retrieval of data (68P20)

Related Items

A unified algorithm for finding maximum and minimum object enclosing rectangles and cuboids ⋮ Half-plane point retrieval queries with independent and dependent geometric uncertainties ⋮ Linear space data structures for two types of range search

Cites Work

• Unnamed Item
• Halfplanar range search in linear space and \(O(n^{0.695})\) query time
• Polygonal intersection searching
• A note on Euclidean near neighbor searching in the plane
• On the shape of a set of points in the plane
• New Data Structures for Orthogonal Range Queries