TWO-DIMENSIONAL RANGE SEARCH BASED ON THE VORONOI DIAGRAM

DOI10.1142/S0218195905001634zbMath1067.68161OpenAlexW2151563658MaRDI QIDQ5311631

Takeshi Kanda, Kōkichi Sugihara

Publication date: 23 August 2005

Published in: International Journal of Computational Geometry & Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0218195905001634

zbMATH Keywords

Voronoi diagramRange searchside-trip facility search

Mathematics Subject Classification ID

Computational aspects related to convexity (52B55) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cites Work

• Halfplanar range search in linear space and \(O(n^{0.695})\) query time
• The complexity of finding fixed-radius near neighbors
• New upper bounds for neighbor searching
• Multidimensional binary search trees used for associative searching