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

Boris Aronov

doi:10.1007/BF01553882

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

Boris Aronov

Research output: Contribution to journal › Article › peer-review

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) log n)-time algorithm for solving this problem and sketch a faster O((n + k) 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)
Pages (from-to)	109-140
Number of pages	32
Journal	Algorithmica
Volume	4
Issue number	1-4
DOIs	https://doi.org/10.1007/BF01553882
State	Published - Jun 1989

Keywords

Computational geometry
Geodesic metric
Shortest paths
Simple polygons
Voronoi diagrams

ASJC Scopus subject areas

Computer Science(all)
Computer Science Applications
Applied Mathematics

Access to Document

10.1007/BF01553882

Cite this

@article{23b157220e134cba8ba743c6b2ef4783,

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) log(n + k) log n)-time algorithm for solving this problem and sketch a faster O((n + k) log(n + k)) algorithm for the case when the set of sites includes all reflex vertices of the polygon in question.",

keywords = "Computational geometry, Geodesic metric, Shortest paths, Simple polygons, Voronoi diagrams",

author = "Boris Aronov",

year = "1989",

month = jun,

doi = "10.1007/BF01553882",

language = "English (US)",

volume = "4",

pages = "109--140",

journal = "Algorithmica",

issn = "0178-4617",

publisher = "Springer New York",

number = "1-4",

}

TY - JOUR

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

AU - Aronov, Boris

PY - 1989/6

Y1 - 1989/6

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) log(n + k) log n)-time algorithm for solving this problem and sketch a faster O((n + k) 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) log(n + k) log n)-time algorithm for solving this problem and sketch a faster O((n + k) log(n + k)) algorithm for the case when the set of sites includes all reflex vertices of the polygon in question.

KW - Computational geometry

KW - Geodesic metric

KW - Shortest paths

KW - Simple polygons

KW - Voronoi diagrams

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

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

U2 - 10.1007/BF01553882

DO - 10.1007/BF01553882

M3 - Article

AN - SCOPUS:0024774085

SN - 0178-4617

VL - 4

SP - 109

EP - 140

JO - Algorithmica

JF - Algorithmica

IS - 1-4

ER -

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

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this