---
res:
bibo_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@eng
bibo_authorlist:
- foaf_Person:
foaf_givenName: Herbert
foaf_name: Herbert Edelsbrunner
foaf_surname: Edelsbrunner
foaf_workInfoHomepage: http://www.librecat.org/personId=3FB178DA-F248-11E8-B48F-1D18A9856A87
orcid: 0000-0002-9823-6833
- foaf_Person:
foaf_givenName: Leonidas
foaf_name: Guibas, Leonidas J
foaf_surname: Guibas
- foaf_Person:
foaf_givenName: Jorge
foaf_name: Stolfi, Jorge
foaf_surname: Stolfi
bibo_doi: 10.1137/0215023
bibo_issue: '2'
bibo_volume: 15
dct_date: 1986^xs_gYear
dct_publisher: SIAM@
dct_title: Optimal point location in a monotone subdivision@
...