A Linear-Time Algorithm for the Geodesic Center of a Simple Polygon

Hee Kap Ahn; Luis Barba; Prosenjit Bose; Jean Lou De Carufel; Matias Korman; Eunjin Oh

doi:10.1007/s00454-016-9796-0

A Linear-Time Algorithm for the Geodesic Center of a Simple Polygon

Hee Kap Ahn, Luis Barba, Prosenjit Bose, Jean Lou De Carufel, Matias Korman, Eunjin Oh

INF - System Information Sciences

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

21 Citations (Scopus)

Abstract

Let P be a closed simple polygon with n vertices. For any two points in P, the geodesic distance between them is the length of the shortest path that connects them among all paths contained in P. The geodesic center of P is the unique point in P that minimizes the largest geodesic distance to all other points of P. In 1989, Pollack et al. (Discrete Comput Geom 4(1): 611–626, 1989) showed an O(nlog n) -time algorithm that computes the geodesic center of P. Since then, a longstanding question has been whether this running time can be improved. In this paper we affirmatively answer this question and present a deterministic linear-time algorithm to solve this problem.

Original language	English
Pages (from-to)	836-859
Number of pages	24
Journal	Discrete and Computational Geometry
Volume	56
Issue number	4
DOIs	https://doi.org/10.1007/s00454-016-9796-0
Publication status	Published - 2016 Dec 1

Keywords

Facility location
Geodesic distance
Simple polygons

ASJC Scopus subject areas

Theoretical Computer Science
Geometry and Topology
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Access to Document

10.1007/s00454-016-9796-0

Cite this

@article{2e54af76909b4ee8af0f02ae7c028c41,

title = "A Linear-Time Algorithm for the Geodesic Center of a Simple Polygon",

abstract = "Let P be a closed simple polygon with n vertices. For any two points in P, the geodesic distance between them is the length of the shortest path that connects them among all paths contained in P. The geodesic center of P is the unique point in P that minimizes the largest geodesic distance to all other points of P. In 1989, Pollack et al. (Discrete Comput Geom 4(1): 611–626, 1989) showed an O(nlog n) -time algorithm that computes the geodesic center of P. Since then, a longstanding question has been whether this running time can be improved. In this paper we affirmatively answer this question and present a deterministic linear-time algorithm to solve this problem.",

keywords = "Facility location, Geodesic distance, Simple polygons",

author = "Ahn, {Hee Kap} and Luis Barba and Prosenjit Bose and {De Carufel}, {Jean Lou} and Matias Korman and Eunjin Oh",

note = "Funding Information: H.-K. Ahn and E. Oh: Supported by the NRF Grant 2011-0030044 (SRC-GAIA) funded by the Korea government (MSIP). M. K. was supported in part by the ELC Project (MEXT KAKENHI Nos. 12H00855 and 15H02665). Publisher Copyright: {\textcopyright} 2016, Springer Science+Business Media New York.",

year = "2016",

month = dec,

day = "1",

doi = "10.1007/s00454-016-9796-0",

language = "English",

volume = "56",

pages = "836--859",

journal = "Discrete and Computational Geometry",

issn = "0179-5376",

publisher = "Springer New York",

number = "4",

}

TY - JOUR

T1 - A Linear-Time Algorithm for the Geodesic Center of a Simple Polygon

AU - Ahn, Hee Kap

AU - Barba, Luis

AU - Bose, Prosenjit

AU - De Carufel, Jean Lou

AU - Korman, Matias

AU - Oh, Eunjin

N1 - Funding Information: H.-K. Ahn and E. Oh: Supported by the NRF Grant 2011-0030044 (SRC-GAIA) funded by the Korea government (MSIP). M. K. was supported in part by the ELC Project (MEXT KAKENHI Nos. 12H00855 and 15H02665). Publisher Copyright: © 2016, Springer Science+Business Media New York.

PY - 2016/12/1

Y1 - 2016/12/1

N2 - Let P be a closed simple polygon with n vertices. For any two points in P, the geodesic distance between them is the length of the shortest path that connects them among all paths contained in P. The geodesic center of P is the unique point in P that minimizes the largest geodesic distance to all other points of P. In 1989, Pollack et al. (Discrete Comput Geom 4(1): 611–626, 1989) showed an O(nlog n) -time algorithm that computes the geodesic center of P. Since then, a longstanding question has been whether this running time can be improved. In this paper we affirmatively answer this question and present a deterministic linear-time algorithm to solve this problem.

AB - Let P be a closed simple polygon with n vertices. For any two points in P, the geodesic distance between them is the length of the shortest path that connects them among all paths contained in P. The geodesic center of P is the unique point in P that minimizes the largest geodesic distance to all other points of P. In 1989, Pollack et al. (Discrete Comput Geom 4(1): 611–626, 1989) showed an O(nlog n) -time algorithm that computes the geodesic center of P. Since then, a longstanding question has been whether this running time can be improved. In this paper we affirmatively answer this question and present a deterministic linear-time algorithm to solve this problem.

KW - Facility location

KW - Geodesic distance

KW - Simple polygons

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

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

U2 - 10.1007/s00454-016-9796-0

DO - 10.1007/s00454-016-9796-0

M3 - Article

AN - SCOPUS:84978152357

SN - 0179-5376

VL - 56

SP - 836

EP - 859

JO - Discrete and Computational Geometry

JF - Discrete and Computational Geometry

IS - 4

ER -

A Linear-Time Algorithm for the Geodesic Center of a Simple Polygon

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this