Optimal Expected-Case Planar Point Location
From MaRDI portal
Publication:5386214
DOI10.1137/S0097539704446724zbMath1137.68021MaRDI 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)
entropy; point location; entropy-preserving cuttings; expected-case complexity; polygonal subdivision; trapezoidal maps
Related Items
Adaptive Point Location in Planar Convex Subdivisions, Distance-sensitive planar point location, On constant factors in comparison-based geometric algorithms and data structures, Biased range trees, Lower bounds for expected-case planar point location, A History of Distribution-Sensitive Data Structures