---
_id: '4104'
abstract:
- lang: eng
  text: "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"
acknowledgement: We would like to thank Andrei Broder, Dan Greene, Mary Claire van
  Leunen, Greg Nelson, Lyle Ramshaw, and F. Frances Yao, whose comments and suggestions
  have greatly improved the readability of this paper.
article_processing_charge: No
article_type: original
author:
- first_name: Herbert
  full_name: Edelsbrunner, Herbert
  id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
  last_name: Edelsbrunner
  orcid: 0000-0002-9823-6833
- first_name: Leonidas
  full_name: Guibas, Leonidas
  last_name: Guibas
- first_name: Jorge
  full_name: Stolfi, Jorge
  last_name: Stolfi
citation:
  ama: 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>
  apa: 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>
  chicago: 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>.
  ieee: 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.
  ista: Edelsbrunner H, Guibas L, Stolfi J. 1986. Optimal point location in a monotone
    subdivision. SIAM Journal on Computing. 15(2), 317–340.
  mla: 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>.
  short: H. Edelsbrunner, L. Guibas, J. Stolfi, SIAM Journal on Computing 15 (1986)
    317–340.
date_created: 2018-12-11T12:06:58Z
date_published: 1986-01-01T00:00:00Z
date_updated: 2022-02-01T10:05:55Z
day: '01'
doi: 10.1137/0215023
extern: '1'
intvolume: '        15'
issue: '2'
language:
- iso: eng
month: '01'
oa_version: None
page: 317 - 340
publication: SIAM Journal on Computing
publication_identifier:
  eissn:
  - 1095-7111
  issn:
  - 0097-5397
publication_status: published
publisher: SIAM
publist_id: '2016'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Optimal point location in a monotone subdivision
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 15
year: '1986'
...