Optimal Expected-Case Planar Point Location

DOI10.1137/S0097539704446724zbMath1137.68021OpenAlexW2150580945MaRDI QIDQ5386214

David M. Mount, Sunil Arya, Ka-Chun Wong, Theocharis Malamatos

Publication date: 22 April 2008

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539704446724

zbMATH Keywords

entropypoint locationentropy-preserving cuttingsexpected-case complexitypolygonal subdivisiontrapezoidal maps

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Searching and sorting (68P10) Data structures (68P05)

Related Items (7)

Distance-sensitive planar point location ⋮ Adaptive Point Location in Planar Convex Subdivisions ⋮ Biased range trees ⋮ Lower bounds for expected-case planar point location ⋮ A History of Distribution-Sensitive Data Structures ⋮ Adaptive Planar Point Location ⋮ On constant factors in comparison-based geometric algorithms and data structures

This page was built for publication: Optimal Expected-Case Planar Point Location