[comp.theory] Visibility Graph

ahsanabd@sal-sun18.usc.edu (Ahsan Abdullah) (04/03/91)

From: ahsanabd@sal-sun18.usc.edu (Ahsan Abdullah)
Newsgroups: comp.theory
Subject: Visibility Graph
Expires: 5th May 1991
References: 
Sender: 
Followup-To: 
Distribution: world
Organization: University of Southern California, Los Angeles, CA
Keywords: Visibility, Computational Geometry

Is there an algorithm faster than the one by Ghosh and Mount (Foundations of

Computer Science 1987) to generate the visibility graph of disjoint polygons?

Note that the time complexity of their algorithm is O(n log n + E), n is the

number of vertices of the polygons, and E could be O(n^2).


Thanks in advance,

Ahsan.