A Sweep-Line Algorithm for the Inclusion Hierarchy among Circles
Kim, Deok-Soo ; Lee, Byunghoon ; Sugihara, Kokichi
Japan J. Indust. Appl. Math., Tome 23 (2006) no. 1, p. 127-138 / Harvested from Project Euclid
Text on Project Euclid
PDF
Alt PDF
Suppose that there are a number of circles in a plane and some of them may contain several smaller circles. In this case, it is necessary to find the inclusion hierarchy among circles for the various applications such as the simulation of emulsion and diameter estimation for wire bundles. In this paper, we present a plane-sweep algorithm that can identify the inclusion hierarchy among the circles in $O(n\log n)$ time in the worst-case. Also, the proposed algorithm uses the sweep-line method and a red-black tree for the efficient computation.
Publié le : 2006-02-14
Classification:  nesting of circles,  plane sweep,  red-black,  interval search,  computational geometry 
@article{1150725475,
     author = {Kim, Deok-Soo and Lee, Byunghoon and Sugihara, Kokichi},
     title = {A Sweep-Line Algorithm for the Inclusion Hierarchy among Circles},
     journal = {Japan J. Indust. Appl. Math.},
     volume = {23},
     number = {1},
     year = {2006},
     pages = { 127-138},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1150725475}
}

Kim, Deok-Soo; Lee, Byunghoon; Sugihara, Kokichi. A Sweep-Line Algorithm for the Inclusion Hierarchy among Circles. Japan J. Indust. Appl. Math., Tome 23 (2006) no. 1, pp.  127-138. http://gdmltest.u-ga.fr/item/1150725475/