We show that the k free bitangents of a collection of n pairwise disjoint convex plane sets can be computed in time O(k + n log n) and O(n) working space. The algorithm uses only one advanced data structure, namely a splittable queue. We introduce (weakly) greedy pseudo-triangulations, whose combinatorial properties are crucial for our method.
|Title of host publication||EPRINTS-BOOK-TITLE|
|Publisher||University of Groningen, Johann Bernoulli Institute for Mathematics and Computer Science|
|Number of pages||10|
|Publication status||Published - 1995|