article published yes Herbert Edelsbrunner author 3FB178DA-F248-11E8-B48F-1D18A9856A870000-0002-9823-6833 Leonidas Guibas author Jorge Stolfi author 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 SIAM1986 eng 0097-5397 1095-711110.1137/0215023 152317 - 340 yes Edelsbrunner, Herbert, Leonidas Guibas, and Jorge Stolfi. “Optimal Point Location in a Monotone Subdivision.” <i>SIAM Journal on Computing</i>. SIAM, 1986. <a href="https://doi.org/10.1137/0215023">https://doi.org/10.1137/0215023</a>. 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> H. Edelsbrunner, L. Guibas, J. Stolfi, SIAM Journal on Computing 15 (1986) 317–340. Edelsbrunner H, Guibas L, Stolfi J. 1986. Optimal point location in a monotone subdivision. SIAM Journal on Computing. 15(2), 317–340. Edelsbrunner, H., Guibas, L., &#38; Stolfi, J. (1986). Optimal point location in a monotone subdivision. <i>SIAM Journal on Computing</i>. SIAM. <a href="https://doi.org/10.1137/0215023">https://doi.org/10.1137/0215023</a> Edelsbrunner, Herbert, et al. “Optimal Point Location in a Monotone Subdivision.” <i>SIAM Journal on Computing</i>, vol. 15, no. 2, SIAM, 1986, pp. 317–40, doi:<a href="https://doi.org/10.1137/0215023">10.1137/0215023</a>. H. Edelsbrunner, L. Guibas, and J. Stolfi, “Optimal point location in a monotone subdivision,” <i>SIAM Journal on Computing</i>, vol. 15, no. 2. SIAM, pp. 317–340, 1986. 41042018-12-11T12:06:58Z2022-02-01T10:05:55Z