---
_id: '4110'
abstract:
- lang: eng
  text: For H a set of lines in the Euclidean plane, $A(H)$ denotes the induced dissection,
    called the arrangement of H. We define the notion of a belt in $A(H)$, which is
    bounded by a subset of the edges in $A(H)$, and describe two algorithms for constructing
    belts. All this is motivated by applications to a host of seemingly unrelated
    problems including a type of range search and finding the minimum area triangle
    with the vertices taken from some finite set of points.
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: Emo
  full_name: Welzl, Emo
  last_name: Welzl
citation:
  ama: Edelsbrunner H, Welzl E. Constructing belts in two-dimensional arrangements
    with applications. <i>SIAM Journal on Computing</i>. 1986;15(1):271-284. doi:<a
    href="https://doi.org/10.1137/0215019">10.1137/0215019</a>
  apa: Edelsbrunner, H., &#38; Welzl, E. (1986). Constructing belts in two-dimensional
    arrangements with applications. <i>SIAM Journal on Computing</i>. SIAM. <a href="https://doi.org/10.1137/0215019">https://doi.org/10.1137/0215019</a>
  chicago: Edelsbrunner, Herbert, and Emo Welzl. “Constructing Belts in Two-Dimensional
    Arrangements with Applications.” <i>SIAM Journal on Computing</i>. SIAM, 1986.
    <a href="https://doi.org/10.1137/0215019">https://doi.org/10.1137/0215019</a>.
  ieee: H. Edelsbrunner and E. Welzl, “Constructing belts in two-dimensional arrangements
    with applications,” <i>SIAM Journal on Computing</i>, vol. 15, no. 1. SIAM, pp.
    271–284, 1986.
  ista: Edelsbrunner H, Welzl E. 1986. Constructing belts in two-dimensional arrangements
    with applications. SIAM Journal on Computing. 15(1), 271–284.
  mla: Edelsbrunner, Herbert, and Emo Welzl. “Constructing Belts in Two-Dimensional
    Arrangements with Applications.” <i>SIAM Journal on Computing</i>, vol. 15, no.
    1, SIAM, 1986, pp. 271–84, doi:<a href="https://doi.org/10.1137/0215019">10.1137/0215019</a>.
  short: H. Edelsbrunner, E. Welzl, SIAM Journal on Computing 15 (1986) 271–284.
date_created: 2018-12-11T12:07:00Z
date_published: 1986-01-01T00:00:00Z
date_updated: 2022-02-01T09:34:20Z
day: '01'
doi: 10.1137/0215019
extern: '1'
intvolume: '        15'
issue: '1'
language:
- iso: eng
month: '01'
oa_version: None
page: 271 - 284
publication: SIAM Journal on Computing
publication_identifier:
  eissn:
  - 1095-7111
  issn:
  - 0097-5397
publication_status: published
publisher: SIAM
publist_id: '2014'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Constructing belts in two-dimensional arrangements with applications
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 15
year: '1986'
...