Constructing belts in two-dimensional arrangements with applications

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 application...

Full description

Saved in:
Bibliographic Details
Published in:SIAM journal on computing 1986-02, Vol.15 (1), p.271-284
Main Authors: EDELSBRUNNER, H, WELZL, E
Format: Article
Language:English
Subjects:
Algorithmics. Computability. Computer arithmetics
Algorithms
Applied sciences
Computer science
control theory
systems
Exact sciences and technology
Theoretical computing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0097-5397
1095-7111
DOI:10.1137/0215019