Constructing belts in two-dimensional arrangements with applications
Herbert Edelsbrunner
Welzl, Emo
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
SIAM
1986
info:eu-repo/semantics/article
doc-type:article
text
https://research-explorer.app.ist.ac.at/record/4110
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>
info:eu-repo/semantics/altIdentifier/doi/10.1137/0215019
info:eu-repo/semantics/closedAccess