ISSN:
1432-0541
Schlagwort(e):
Computational geometry
;
Visibility graph
;
Shortest path
Quelle:
Springer Online Journal Archives 1860-2000
Thema:
Informatik
,
Mathematik
Notizen:
Abstract AnO(¦E¦log2 n) algorithm is presented to construct the visibility graph for a collection ofn nonintersecting line segments, where ¦E¦ is the number of edges in the visibility graph. This algorithm is much faster than theO(n 2)-time andO(n 2)-space algorithms by Asanoet al., and by Welzl, on sparse visibility graphs. Thus we partially resolve an open problem raised by Welzl. Further, our algorithm uses onlyO(n) working storage.
Materialart:
Digitale Medien
URL:
http://dx.doi.org/10.1007/BF01840385
