Optimal point location in a monotone subdivision

H. Edelsbrunner, L. Guibas, J. Stolfi, SIAM Journal on Computing 15 (1986) 317–340.

Download
No fulltext has been uploaded. References only!

Journal Article | Published
Author
; ;
Abstract
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
Publishing Year
Date Published
1986-01-01
Journal Title
SIAM Journal on Computing
Volume
15
Issue
2
Page
317 - 340
IST-REx-ID

Cite this

Edelsbrunner H, Guibas L, Stolfi J. Optimal point location in a monotone subdivision. SIAM Journal on Computing. 1986;15(2):317-340. doi:10.1137/0215023
Edelsbrunner, H., Guibas, L., & Stolfi, J. (1986). Optimal point location in a monotone subdivision. SIAM Journal on Computing, 15(2), 317–340. https://doi.org/10.1137/0215023
Edelsbrunner, Herbert, Leonidas Guibas, and Jorge Stolfi. “Optimal Point Location in a Monotone Subdivision.” SIAM Journal on Computing 15, no. 2 (1986): 317–40. https://doi.org/10.1137/0215023.
H. Edelsbrunner, L. Guibas, and J. Stolfi, “Optimal point location in a monotone subdivision,” SIAM Journal on Computing, vol. 15, no. 2, pp. 317–340, 1986.
Edelsbrunner H, Guibas L, Stolfi J. 1986. Optimal point location in a monotone subdivision. SIAM Journal on Computing. 15(2), 317–340.
Edelsbrunner, Herbert, et al. “Optimal Point Location in a Monotone Subdivision.” SIAM Journal on Computing, vol. 15, no. 2, SIAM, 1986, pp. 317–40, doi:10.1137/0215023.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar