IDA Dept. of Computer and Information science, Linköping University

IDA Technical Reports: abstract

Generated: Sat, 26 Jul 2014 13:11:58

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).

Goto (at Linköping University): CS Dept TR Overview