A simple entropy-based algorithm for planar point location

DOI10.1145/1240233.1240240zbMath1321.68429OpenAlexW2133718007MaRDI QIDQ2944554

Sunil Arya, Theocharis Malamatos, David M. Mount

Publication date: 2 September 2015

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: http://repository.ust.hk/ir/bitstream/1783.1-3136/1/simple.pdf

zbMATH Keywords

entropyrandomized algorithmspoint locationexpected-case complexitypolygonal subdivisiontrapezoidal maps

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Data structures (68P05) Randomized algorithms (68W20)

Related Items (5)

Distance-sensitive planar point location ⋮ Practical distribution-sensitive point location in triangulations ⋮ Adaptive Point Location in Planar Convex Subdivisions ⋮ Lower bounds for expected-case planar point location ⋮ Adaptive Planar Point Location

This page was built for publication: A simple entropy-based algorithm for planar point location