TY - GEN

T1 - On the geodesic Voronoi diagram of point sites in a simple polygon

AU - Aronov, Boris

N1 - Publisher Copyright:
© 1987 ACM.

PY - 1987/10/1

Y1 - 1987/10/1

N2 - Given a simple polygon with n sides in the plane and a set of k point "sites" in its interior or on the boundary, compute the Voronoi diagram of the set of sites using the internal "geodesic" distance inside the polygon as the metric. We describe an O ((n+k )log2(n+k)) time algorithm for solving this problem and sketch a faster 0((n+t)log(n+k)) algorithm for the case when the set of sites includes all reflex vertices of the polygon in question.

AB - Given a simple polygon with n sides in the plane and a set of k point "sites" in its interior or on the boundary, compute the Voronoi diagram of the set of sites using the internal "geodesic" distance inside the polygon as the metric. We describe an O ((n+k )log2(n+k)) time algorithm for solving this problem and sketch a faster 0((n+t)log(n+k)) algorithm for the case when the set of sites includes all reflex vertices of the polygon in question.

UR - http://www.scopus.com/inward/record.url?scp=84893389797&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84893389797&partnerID=8YFLogxK

U2 - 10.1145/41958.41963

DO - 10.1145/41958.41963

M3 - Conference contribution

AN - SCOPUS:84893389797

T3 - Proceedings of the 3rd Annual Symposium on Computational Geometry, SCG 1987

SP - 39

EP - 49

BT - Proceedings of the 3rd Annual Symposium on Computational Geometry, SCG 1987

A2 - Soule, D.

PB - Association for Computing Machinery, Inc

T2 - 3rd Annual Symposium on Computational Geometry, SCG 1987

Y2 - 8 June 1987 through 10 June 1987

ER -