Computing the L1 geodesic diameter and center of a simple polygon in linear time

被引：7

作者：

Bae, Sang Won ^{[1
]}

Korman, Matias ^{[2
,3
]}

Okamoto, Yoshio ^{[4
]}

Wang, Haitao ^{[5
]}

机构：

[1] Kyonggi Univ, Suwon, South Korea

[2] Natl Inst Informat, Tokyo, Japan

[3] JST, Kawarabayashi Large Graph Project, ERATO, Tokyo, Japan

[4] Univ Electrocommun, Tokyo, Japan

[5] Utah State Univ, Logan, UT 84322 USA

来源：

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS | 2015年 / 48卷 / 06期

基金：

日本学术振兴会; 美国国家科学基金会; 新加坡国家研究基金会;

关键词：

Simple polygon; Geodesic diameter; Geodesic center; L1; metric; LINK CENTER; ALGORITHM;

D O I：

10.1016/j.comgeo.2015.02.005

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

In this paper, we show that the L-1 geodesic diameter and center of a simple polygon can be computed in linear time. For the purpose, we focus on revealing basic geometric properties of the L-1 geodesic balls, that is, the metric balls with respect to the L-1 geodesic distance. More specifically, in this paper we show that any family of L-1 geodesic balls in any simple polygon has Helly number two, and the L-1 geodesic center consists of midpoints of shortest paths between diametral pairs. These properties are crucial for our linear-time algorithms, and do not hold for the Euclidean case. (C) 2015 Elsevier B.V. All rights reserved.

引用

页码：495 / 505

页数：11

共 21 条

[1] GEOMETRIC APPLICATIONS OF A MATRIX-SEARCHING ALGORITHM [J].