Optimal point location in a monotone subdivision Edelsbrunner, Herbert ; https://orcid.org/0000-0002-9823-6833 Guibas, Leonidas Stolfi, Jorge Point location, often known in graphics as “hit detection,” is one of the fundamental problems of computational geometry. In a point location query we want to identify which of a given collection of geometric objects contains a particular point. Let $\mathcal{S}$ denote a subdivision of the Euclidean plane into monotone regions by a straight-line graph of $m$ edges. In this paper we exhibit a substantial refinement of the technique of Lee and Preparata [SIAM J. Comput., 6 (1977), pp. 594–606] for locating a point in $\mathcal{S}$ based on separating chains. The new data structure, called a layered dag, can be built in $O(m)$ time, uses $O(m)$ storage, and makes possible point location in $O(\log m)$ time. Unlike previous structures that attain these optimal bounds, the layered dag can be implemented in a simple and practical way, and is extensible to subdivisions with edges more general than straight-line segments. © 1986 Society for Industrial and Applied Mathematics SIAM 1986 info:eu-repo/semantics/article doc-type:article text http://purl.org/coar/resource_type/c_2df8fbb1 https://research-explorer.ista.ac.at/record/4104 Edelsbrunner H, Guibas L, Stolfi J. Optimal point location in a monotone subdivision. <i>SIAM Journal on Computing</i>. 1986;15(2):317-340. doi:<a href="https://doi.org/10.1137/0215023">10.1137/0215023</a> eng info:eu-repo/semantics/altIdentifier/doi/10.1137/0215023 info:eu-repo/semantics/altIdentifier/issn/0097-5397 info:eu-repo/semantics/altIdentifier/e-issn/1095-7111 info:eu-repo/semantics/closedAccess