Computing the L1 Geodesic Diameter and Center of a Polygonal Domain

Sang Won Bae; Matias Korman; Joseph S.B. Mitchell; Yoshio Okamoto; Valentin Polishchuk; Haitao Wang

doi:10.1007/s00454-016-9841-z

Computing the L₁ Geodesic Diameter and Center of a Polygonal Domain

Sang Won Bae
, Matias Korman
, Joseph S.B. Mitchell
, Yoshio Okamoto
, Valentin Polishchuk
, Haitao Wang

Applied Mathematics and Statistics

Kyonggi University
Tohoku University
The University of Electro-Communications
Linköping University
Utah State University

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

3 Scopus citations

Abstract

For a polygonal domain with h holes and a total of n vertices, we present algorithms that compute the L₁ geodesic diameter in O(n²+ h⁴) time and the L₁ geodesic center in O((n⁴+ n²h⁴) α(n)) time, respectively, where α(·) denotes the inverse Ackermann function. No algorithms were known for these problems before. For the Euclidean counterpart, the best algorithms compute the geodesic diameter in O(n^7.73) or O(n⁷(h+ log n)) time, and compute the geodesic center in O(n¹¹log n) time. Therefore, our algorithms are significantly faster than the algorithms for the Euclidean problems. Our algorithms are based on several interesting observations on L₁ shortest paths in polygonal domains.

Original language	English
Pages (from-to)	674-701
Number of pages	28
Journal	Discrete and Computational Geometry
Volume	57
Issue number	3
DOIs	https://doi.org/10.1007/s00454-016-9841-z
State	Published - Apr 1 2017

Keywords

Geodesic center
Geodesic diameter
L metric
Polygonal domains
Shortest paths

Access to Document

10.1007/s00454-016-9841-z

Cite this

@article{cde4906ab03e42559211946f2b5e4134,

title = "Computing the L1 Geodesic Diameter and Center of a Polygonal Domain",

abstract = "For a polygonal domain with h holes and a total of n vertices, we present algorithms that compute the L1 geodesic diameter in O(n2+ h4) time and the L1 geodesic center in O((n4+ n2h4) α(n)) time, respectively, where α(·) denotes the inverse Ackermann function. No algorithms were known for these problems before. For the Euclidean counterpart, the best algorithms compute the geodesic diameter in O(n7.73) or O(n7(h+ log n)) time, and compute the geodesic center in O(n11log n) time. Therefore, our algorithms are significantly faster than the algorithms for the Euclidean problems. Our algorithms are based on several interesting observations on L1 shortest paths in polygonal domains.",

keywords = "Geodesic center, Geodesic diameter, L metric, Polygonal domains, Shortest paths",

author = "Bae, \{Sang Won\} and Matias Korman and Mitchell, \{Joseph S.B.\} and Yoshio Okamoto and Valentin Polishchuk and Haitao Wang",

note = "Publisher Copyright: {\textcopyright} 2016, Springer Science+Business Media New York.",

year = "2017",

month = apr,

day = "1",

doi = "10.1007/s00454-016-9841-z",

language = "English",

volume = "57",

pages = "674--701",

journal = "Discrete and Computational Geometry",

issn = "0179-5376",

number = "3",

}

TY - JOUR

T1 - Computing the L1 Geodesic Diameter and Center of a Polygonal Domain

AU - Bae, Sang Won

AU - Korman, Matias

AU - Mitchell, Joseph S.B.

AU - Okamoto, Yoshio

AU - Polishchuk, Valentin

AU - Wang, Haitao

PY - 2017/4/1

Y1 - 2017/4/1

N2 - For a polygonal domain with h holes and a total of n vertices, we present algorithms that compute the L1 geodesic diameter in O(n2+ h4) time and the L1 geodesic center in O((n4+ n2h4) α(n)) time, respectively, where α(·) denotes the inverse Ackermann function. No algorithms were known for these problems before. For the Euclidean counterpart, the best algorithms compute the geodesic diameter in O(n7.73) or O(n7(h+ log n)) time, and compute the geodesic center in O(n11log n) time. Therefore, our algorithms are significantly faster than the algorithms for the Euclidean problems. Our algorithms are based on several interesting observations on L1 shortest paths in polygonal domains.

AB - For a polygonal domain with h holes and a total of n vertices, we present algorithms that compute the L1 geodesic diameter in O(n2+ h4) time and the L1 geodesic center in O((n4+ n2h4) α(n)) time, respectively, where α(·) denotes the inverse Ackermann function. No algorithms were known for these problems before. For the Euclidean counterpart, the best algorithms compute the geodesic diameter in O(n7.73) or O(n7(h+ log n)) time, and compute the geodesic center in O(n11log n) time. Therefore, our algorithms are significantly faster than the algorithms for the Euclidean problems. Our algorithms are based on several interesting observations on L1 shortest paths in polygonal domains.

KW - Geodesic center

KW - Geodesic diameter

KW - L metric

KW - Polygonal domains

KW - Shortest paths

UR - https://www.scopus.com/pages/publications/84996536583

U2 - 10.1007/s00454-016-9841-z

DO - 10.1007/s00454-016-9841-z

M3 - Article

AN - SCOPUS:84996536583

SN - 0179-5376

VL - 57

SP - 674

EP - 701

JO - Discrete and Computational Geometry

JF - Discrete and Computational Geometry

IS - 3

ER -

Computing the L₁ Geodesic Diameter and Center of a Polygonal Domain

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this