Personal tools
You are here: Home Projects Internal Projects On-line Zone Construction
« June 2017 »
June
SuMoTuWeThFrSa
123
45678910
11121314151617
18192021222324
252627282930
Log in


Forgot your password?
 

On-line Zone Construction in Arrangements

[On-line Zone Construction]

Abstract

Given a finite set L of lines in the plane we wish to compute the zone of an additional curve c in the arrangement A(L), namely the set of faces of the planar subdivision induced by the lines in L that are crossed by c, where c 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.

Links

  • C. Linhart, D. Halperin, S. Har-Peled and I. Hanniel
    On-Line Zone Construction in Arrangements of Lines in the Plane
    International Journal of Computational Geometry and Applications, 13(6):  463-485, 2003 [link] [bibtex]
    A preliminary version with Y. Aharoni appeared in Proceedings of the 3rd International Workshop on Algorithm Engineering (WAE),  1668: 139-153, Springer, LNCS, London, 1999, [link] [bibtex]
  • Sariel Har-Peled
    Taking a Walk in a Planar Arrangement
    SIAM Journal on Computing, 30(4): 1341-1367, 2000 [link] [bibtex]

Contact

Chaim Linhart http://www.math.tau.ac.il/~chaim chaim@post.tau.ac.il
Document Actions