Name
Title | ||
|---|---|---|
An Experimental Study Of On-Line Methods For Zone Construction In Arrangements Of Lines In The Plane |
Abstract | ||
|---|---|---|
Given a finite set L of lines in the plane we wish to compute the zone of an additional curve gamma in the arrangement A(L), namely the set of faces of the planar subdivision induced by the lines in L that are crossed by gamma, where gamma is not given in advance but rather provided on-line portion by portion. This problem is motivated by the computation of the area bisectors of a polygonal set in the plane. We present four algorithms which solve this problem efficiently and exactly (giving precise results even on degenerate input). Our main algorithm is a novel approach based on the binary space partition technique. We implemented all four algorithms. We present implementation details, comparison of performance, and a discussion of the advantages and shortcomings of each of the proposed algorithms. |
Year | DOI | Venue |
|---|---|---|
2003 | 10.1142/S0218195903001293 | INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS |
Keywords | DocType | Volume |
arrangements of lines, zone, on-line algorithms, binary space partition, half-plane intersection, convex hulls | Journal | 13 |
Issue | ISSN | Citations |
6 | 0218-1959 | 0 |
PageRank | References | Authors |
0.34 | 13 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Chaim Linhart | 1 | 128 | 8.57 |
| Dan Halperin | 2 | 1291 | 105.20 |
| Iddo Hanniel | 3 | 197 | 12.98 |
| Sariel Har-Peled | 4 | 2630 | 191.68 |