@techreport{R-89-04, TITLE = {Voronoi Diagrams with Barriers and the Shortest Diagonal Problem}, AUTHOR = {Andrzej Lingas}, YEAR = {1989}, NUMBER = {R-89-04}, INSTITUTION = ida, ADDRESS = idaaddr, ABSTRACTURL = {/publications/cgi-bin/tr-fetch.pl?r-89-04+abstr}, 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).}, IDANR = {LiTH-IDA-R-89-04}