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

Boris Aronov

doi:10.1145/41958.41963

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

Boris Aronov

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

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 )log²(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.

Original language	English (US)
Title of host publication	Proceedings of the 3rd Annual Symposium on Computational Geometry, SCG 1987
Editors	D. Soule
Publisher	Association for Computing Machinery, Inc
Pages	39-49
Number of pages	11
ISBN (Electronic)	0897912314, 9780897912310
DOIs	https://doi.org/10.1145/41958.41963
State	Published - Oct 1 1987
Event	3rd Annual Symposium on Computational Geometry, SCG 1987 - Waterloo, Canada Duration: Jun 8 1987 → Jun 10 1987

Publication series

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

Other

Other	3rd Annual Symposium on Computational Geometry, SCG 1987
Country/Territory	Canada
City	Waterloo
Period	6/8/87 → 6/10/87

ASJC Scopus subject areas

Geometry and Topology
Computational Mathematics

Access to Document

10.1145/41958.41963

Cite this

On the geodesic Voronoi diagram of point sites in a simple polygon. / Aronov, Boris.
Proceedings of the 3rd Annual Symposium on Computational Geometry, SCG 1987. ed. / D. Soule. Association for Computing Machinery, Inc, 1987. p. 39-49 (Proceedings of the 3rd Annual Symposium on Computational Geometry, SCG 1987).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Aronov, B 1987, On the geodesic Voronoi diagram of point sites in a simple polygon. in D Soule (ed.), Proceedings of the 3rd Annual Symposium on Computational Geometry, SCG 1987. Proceedings of the 3rd Annual Symposium on Computational Geometry, SCG 1987, Association for Computing Machinery, Inc, pp. 39-49, 3rd Annual Symposium on Computational Geometry, SCG 1987, Waterloo, Canada, 6/8/87. https://doi.org/10.1145/41958.41963

@inproceedings{a5ed579fa71548f38c6ebe077175d20a,

title = "On the geodesic Voronoi diagram of point sites in a simple polygon",

abstract = "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.",

author = "Boris Aronov",

note = "Publisher Copyright: {\textcopyright} 1987 ACM.; 3rd Annual Symposium on Computational Geometry, SCG 1987 ; Conference date: 08-06-1987 Through 10-06-1987",

year = "1987",

month = oct,

day = "1",

doi = "10.1145/41958.41963",

language = "English (US)",

series = "Proceedings of the 3rd Annual Symposium on Computational Geometry, SCG 1987",

publisher = "Association for Computing Machinery, Inc",

pages = "39--49",

editor = "D. Soule",

booktitle = "Proceedings of the 3rd Annual Symposium on Computational Geometry, SCG 1987",

}

TY - GEN

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

AU - Aronov, Boris

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 -

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

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this