Author(s):

Edelsbrunner, Herbert; Welzl, Emo

Article Title: 
Constructing belts in twodimensional arrangements with applications

Affiliation 

Abstract: 
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.
© 1986 © Society for Industrial and Applied Mathematics

Keywords: 
computational geometry; planesweep; arrangements of lines; maintenance of convex hulls; efficient algorithms; halfplanar range search

Journal Title:

SIAM Journal on Computing

Volume: 
15

Issue 
1

ISSN:

00975397

Publisher:

SIAM

Date Published:

19860101

Start Page: 
271

End Page:

284

Copyright Statement: 
© Society for Industrial and Applied Mathematics

DOI: 
10.1137/0215019

Open access: 
no 