---
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.\r\n© 1986 Society for Industrial and Applied
    Mathematics@eng"
  bibo_authorlist:
  - foaf_Person:
      foaf_givenName: Herbert
      foaf_name: Edelsbrunner, Herbert
      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
      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_isPartOf:
  - http://id.crossref.org/issn/0097-5397
  - http://id.crossref.org/issn/1095-7111
  dct_language: eng
  dct_publisher: SIAM@
  dct_title: Optimal point location in a monotone subdivision@
...