visibility graph program

Article View: comp.theory

Article #1807

#1807

From: Steve Ratering
Date: Thu, 13 Jun 1991 20:38

7 lines
796 bytes

If you have a computer program that takes as input a set of polygons
in a plane such that the total number of vertices is n, and outputs 
the visibility graph (an edge exists for each pair of vertices (not 
necessarily in the same polygon) which can "see each other") in 
O(n^2 log n) time please email it to me.  Thank you.

Steve Ratering

Technical Details

Message-ID: <1991Jun13.203844.8223@cs.umn.edu>

Path:

arc1-ca.pugleaf.net!utzoo!utgpu!news-server.csri.toronto.edu!rutgers!psuvax1!wuarchive!sdd.hp.com!spool.mu.edu!cs.umn.edu!ratering

Show Full Headers

Complete Article Headers

Path: arc1-ca.pugleaf.net!utzoo!utgpu!news-server.csri.toronto.edu!rutgers!psuvax1!wuarchive!sdd.hp.com!spool.mu.edu!cs.umn.edu!ratering
From: ratering@umn-cs.cs.umn.edu (Steve Ratering)
Newsgroups: comp.theory
Subject: visibility graph program
Message-ID: <1991Jun13.203844.8223@cs.umn.edu>
Date: 13 Jun 91 20:38:44 GMT
Sender: ratering@cs.umn.edu (Steve Ratering)
Distribution: usa
Organization: University of Minnesota, Minneapolis, CSci dept.
Lines: 7