IDA Technical Reports: abstract

Lingas, A. (1989). Voronoi Diagrams with Barriers and the Shortest Diagonal Problem. Technical Report LiTH-IDA-R-89-04, Department of Computer and Information Science, Linköping University, Sweden. (bibtex),

Abstract: Using the concept of a generalized Voronoi diagram to include edge barriers it is shown that a shortest diagonal of a planar straight-line graph can be found in time O(n log n).