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).
CS Dept TR Overview