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

IDA Technical Reports: abstract

Generated: Sun, 20 Apr 2014 13:01:45

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
<webmaster@ida.liu.se>