Constructing belts in two-dimensional arrangements with applications Journal Article


Author(s): Edelsbrunner, Herbert; Welzl, Emo
Article Title: Constructing belts in two-dimensional 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; plane-sweep; arrangements of lines; maintenance of convex hulls; efficient algorithms; halfplanar range search
Journal Title: SIAM Journal on Computing
Volume: 15
Issue 1
ISSN: 0097-5397
Publisher: SIAM  
Date Published: 1986-01-01
Start Page: 271
End Page: 284
Copyright Statement: © Society for Industrial and Applied Mathematics
DOI: 10.1137/0215019
Open access: no
IST Austria Authors
Related IST Austria Work