ABSTRACT
“Where am I?” is a basic question for many computer applications that employ geometric structures (e.g., in computer graphics, geographic information systems, robotics, and databases). Given a set of disjoint geometric objects, the p o i n t - l o c a t i o n p r o b l e m $ \boldsymbol{point-location problem} $ https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9781315119601/fb8178cb-c53c-4311-b072-eff5ec016aba/content/inline-math38_1.tif"/> asks for the object containing a query point that is specified by its coordinates. Instances of the problem vary in the dimension and type of objects and whether the set is static or dynamic. Classical solutions vary in preprocessing time, space used, and query time. Recent solutions also consider entropy of the query distribution, or exploit randomness, external memory, or capabilities of the word RAM machine model.
