---
_id: '4129'
abstract:
- lang: eng
  text: "An algorithm for the geometric problem of determining a line (called a stabbing
    line) which intersects each ofn given line segments in the plane is presented.
    As a matter of fact, the algorithm computes a description of all stabbing lines.
    A purely geometric fact is proved which infers that this description requiresO(n)
    space to be specified. Our algorithm computes it inO(n logn) time which is optimal
    in the worst case.\r\nUsing the description of the stabbing lines, we are able
    to decide inO(logn) time whether or not a specified line is a stabbing line. Finally,
    the problem of maintaining the description of all stabbing lines while inserting
    and deleting line segments is addressed."
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: Hermann
  full_name: Maurer, Hermann
  last_name: Maurer
- first_name: Franco
  full_name: Preparata, Franco
  last_name: Preparata
- first_name: Arnold
  full_name: Rosenberg, Arnold
  last_name: Rosenberg
- first_name: Emo
  full_name: Welzl, Emo
  last_name: Welzl
- first_name: Derick
  full_name: Wood, Derick
  last_name: Wood
citation:
  ama: Edelsbrunner H, Maurer H, Preparata F, Rosenberg A, Welzl E, Wood D. Stabbing
    line segments. <i>BIT Numerical Mathematics</i>. 1982;22(3):274-281. doi:<a href="https://doi.org/10.1007/BF01934440">10.1007/BF01934440</a>
  apa: Edelsbrunner, H., Maurer, H., Preparata, F., Rosenberg, A., Welzl, E., &#38;
    Wood, D. (1982). Stabbing line segments. <i>BIT Numerical Mathematics</i>. Springer
    Nature. <a href="https://doi.org/10.1007/BF01934440">https://doi.org/10.1007/BF01934440</a>
  chicago: Edelsbrunner, Herbert, Hermann Maurer, Franco Preparata, Arnold Rosenberg,
    Emo Welzl, and Derick Wood. “Stabbing Line Segments.” <i>BIT Numerical Mathematics</i>.
    Springer Nature, 1982. <a href="https://doi.org/10.1007/BF01934440">https://doi.org/10.1007/BF01934440</a>.
  ieee: H. Edelsbrunner, H. Maurer, F. Preparata, A. Rosenberg, E. Welzl, and D. Wood,
    “Stabbing line segments,” <i>BIT Numerical Mathematics</i>, vol. 22, no. 3. Springer
    Nature, pp. 274–281, 1982.
  ista: Edelsbrunner H, Maurer H, Preparata F, Rosenberg A, Welzl E, Wood D. 1982.
    Stabbing line segments. BIT Numerical Mathematics. 22(3), 274–281.
  mla: Edelsbrunner, Herbert, et al. “Stabbing Line Segments.” <i>BIT Numerical Mathematics</i>,
    vol. 22, no. 3, Springer Nature, 1982, pp. 274–81, doi:<a href="https://doi.org/10.1007/BF01934440">10.1007/BF01934440</a>.
  short: H. Edelsbrunner, H. Maurer, F. Preparata, A. Rosenberg, E. Welzl, D. Wood,
    BIT Numerical Mathematics 22 (1982) 274–281.
date_created: 2018-12-11T12:07:06Z
date_published: 1982-09-01T00:00:00Z
date_updated: 2022-01-21T11:01:45Z
day: '01'
doi: 10.1007/BF01934440
extern: '1'
intvolume: '        22'
issue: '3'
language:
- iso: eng
month: '09'
oa_version: None
page: 274 - 281
publication: BIT Numerical Mathematics
publication_identifier:
  eissn:
  - 1572-9125
  issn:
  - 0006-3835
publication_status: published
publisher: Springer Nature
publist_id: '1990'
quality_controlled: '1'
status: public
title: Stabbing line segments
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 22
year: '1982'
...