Optimal Expected-Case Planar Point Location

DOI10.1137/S0097539704446724MaRDI QIDQ5386214zbMATH OpenOpenAlexFDO

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

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

entropyentropy-preserving cuttingsexpected-case complexitypoint locationpolygonal subdivisiontrapezoidal maps

Mathematics Subject Classification ID

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

Recommendations

• Lower bounds for expected-case planar point location
• Entropy-preserving cuttings and space-efficient planar point location
• scientific article; zbMATH DE number 1617272
• Distance-sensitive planar point location
• A simple entropy-based algorithm for planar point location

Cited in

(13)

• Expected asymptotically optimal 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
• scientific article; zbMATH DE number 1617272 (Why is no real title available?)
• Entropy-preserving cuttings and space-efficient planar point location
• A simple entropy-based algorithm for planar point location
• Optimal planar point location
• Distance-sensitive planar point location
• A history of distribution-sensitive data structures
• Entropy, triangulation, and point location in planar subdivisions
• Adaptive planar point location
• Adaptive Point Location in Planar Convex Subdivisions

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

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