Name
Abstract | ||
|---|---|---|
Given a finite set L of lines in the plane we wish to compute the zone of an additional curve γ in the arrangement A(L), namely the set of faces of the planar subdivision induced by the lines in L that are crossed by γ, where γ 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). We implemented the 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 |
|---|---|---|
1999 | 10.1007/3-540-48318-7_13 | Algorithm Engineering |
Keywords | Field | DocType |
on-line zone construction,additional curve,present implementation detail,precise result,area bisectors,on-line portion,finite set,proposed algorithm,planar subdivision | Discrete geometry,Topology,Discrete mathematics,Polygon,Finite set,Convex hull,Algorithm,Subdivision,Planar,Binary search tree,Mathematics,Computation | Conference |
Volume | ISSN | ISBN |
1668 | 0302-9743 | 3-540-66427-0 |
Citations | PageRank | References |
5 | 0.55 | 12 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yuval Aharoni | 1 | 5 | 0.55 |
| Dan Halperin | 2 | 1291 | 105.20 |
| Iddo Hanniel | 3 | 197 | 12.98 |
| Sariel Har-Peled | 4 | 2630 | 191.68 |
| Chaim Linhart | 5 | 128 | 8.57 |