Constructing belts in two-dimensional arrangements with applications

H. Edelsbrunner, E. Welzl, SIAM Journal on Computing 15 (1986) 271–284.

Download
No fulltext has been uploaded. References only!

Journal Article | Published
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
Publishing Year
Date Published
1986-01-01
Journal Title
SIAM Journal on Computing
Volume
15
Issue
1
Page
271 - 284
IST-REx-ID

Cite this

Edelsbrunner H, Welzl E. Constructing belts in two-dimensional arrangements with applications. SIAM Journal on Computing. 1986;15(1):271-284. doi:10.1137/0215019
Edelsbrunner, H., & Welzl, E. (1986). Constructing belts in two-dimensional arrangements with applications. SIAM Journal on Computing, 15(1), 271–284. https://doi.org/10.1137/0215019
Edelsbrunner, Herbert, and Emo Welzl. “Constructing Belts in Two-Dimensional Arrangements with Applications.” SIAM Journal on Computing 15, no. 1 (1986): 271–84. https://doi.org/10.1137/0215019.
H. Edelsbrunner and E. Welzl, “Constructing belts in two-dimensional arrangements with applications,” SIAM Journal on Computing, vol. 15, no. 1, pp. 271–284, 1986.
Edelsbrunner H, Welzl E. 1986. Constructing belts in two-dimensional arrangements with applications. SIAM Journal on Computing. 15(1), 271–284.
Edelsbrunner, Herbert, and Emo Welzl. “Constructing Belts in Two-Dimensional Arrangements with Applications.” SIAM Journal on Computing, vol. 15, no. 1, SIAM, 1986, pp. 271–84, doi:10.1137/0215019.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar