morse@leadsv.UUCP (Terry Morse) (05/02/87)
I am looking for algorithms that can efficiently route around polygonal
obstacles. Does anybody have any pointers? I have found only one
reference:
Clarkson, Kapoor, Vaidya:
"Rectilinear Shortest Paths Through Polygonal Obstacles in
O(n log^2 n) Time"
The authors are from Bell Labs. If any of the authors are out there, would you
please respond to me? I have not been able to locate the paper yet. Many
thanks in advance.
--
Terry Morse (408)743-1487
{ hplabs!cae780 } | { ihnp4!sun!sunncal } !leadsv!morsetrainor@CS.UCLA.EDU (02/16/88)
I have question about a statement in Preparata & Shamos' book about the
DCEL data structure, page 16:
If the graph has N vertices and F faces, we can assume we have two
arrays HV[1:N] and HF[1:F] of headers of the vertex and face lists:
these arrays can be filled by a scan of arrays V1 and F1 in time O(N).
Shouldn't that last part read "scan of arrays V1, V2, F1, and F2"?
Anything else seems to make some assumption about edge orientations.
douglas trainor
I want to thank those of you that responded to my computational geometry
query last year -- about course offerings at your university. UCLA has
since establisted a graduate seminar (cs219) in computational geometry.