---
_id: '4102'
abstract:
- lang: eng
  text: Determining or counting geometric objects that intersect another geometric
    query object is at the core of algorithmic problems in a number of applied areas
    of computer science. This article presents a family of space-efficient data structures
    that realize sublinear query time for points, line segments, lines and polygons
    in the plane, and points, line segments, planes, and polyhedra in three dimensions.
article_processing_charge: No
article_type: original
author:
- first_name: David
  full_name: Dobkin, David
  last_name: Dobkin
- first_name: Herbert
  full_name: Edelsbrunner, Herbert
  id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
  last_name: Edelsbrunner
  orcid: 0000-0002-9823-6833
citation:
  ama: Dobkin D, Edelsbrunner H. Space searching for intersecting objects. <i>Journal
    of Algorithms</i>. 1987;8(3):348-361. doi:<a href="https://doi.org/10.1016/0196-6774(87)90015-0">10.1016/0196-6774(87)90015-0</a>
  apa: Dobkin, D., &#38; Edelsbrunner, H. (1987). Space searching for intersecting
    objects. <i>Journal of Algorithms</i>. Academic Press. <a href="https://doi.org/10.1016/0196-6774(87)90015-0">https://doi.org/10.1016/0196-6774(87)90015-0</a>
  chicago: Dobkin, David, and Herbert Edelsbrunner. “Space Searching for Intersecting
    Objects.” <i>Journal of Algorithms</i>. Academic Press, 1987. <a href="https://doi.org/10.1016/0196-6774(87)90015-0">https://doi.org/10.1016/0196-6774(87)90015-0</a>.
  ieee: D. Dobkin and H. Edelsbrunner, “Space searching for intersecting objects,”
    <i>Journal of Algorithms</i>, vol. 8, no. 3. Academic Press, pp. 348–361, 1987.
  ista: Dobkin D, Edelsbrunner H. 1987. Space searching for intersecting objects.
    Journal of Algorithms. 8(3), 348–361.
  mla: Dobkin, David, and Herbert Edelsbrunner. “Space Searching for Intersecting
    Objects.” <i>Journal of Algorithms</i>, vol. 8, no. 3, Academic Press, 1987, pp.
    348–61, doi:<a href="https://doi.org/10.1016/0196-6774(87)90015-0">10.1016/0196-6774(87)90015-0</a>.
  short: D. Dobkin, H. Edelsbrunner, Journal of Algorithms 8 (1987) 348–361.
date_created: 2018-12-11T12:06:57Z
date_published: 1987-09-01T00:00:00Z
date_updated: 2022-02-03T13:47:53Z
day: '01'
doi: 10.1016/0196-6774(87)90015-0
extern: '1'
intvolume: '         8'
issue: '3'
language:
- iso: eng
main_file_link:
- url: https://www.sciencedirect.com/science/article/pii/0196677487900150?via%3Dihub
month: '09'
oa_version: None
page: 348 - 361
publication: Journal of Algorithms
publication_identifier:
  eissn:
  - 1090-2678
  issn:
  - 0196-6774
publication_status: published
publisher: Academic Press
publist_id: '2024'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Space searching for intersecting objects
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 8
year: '1987'
...