Computing the Visibility Graph via Pseudo-triangulations

Michel Pocchiola, Gert Vegter

Research output: Chapter in Book/Report/Conference proceedingChapterAcademic

38 Citations (Scopus)
267 Downloads (Pure)

Abstract

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.
Original languageEnglish
Title of host publicationEPRINTS-BOOK-TITLE
PublisherUniversity of Groningen, Johann Bernoulli Institute for Mathematics and Computer Science
Number of pages10
Publication statusPublished - 1995

Cite this