The geodesic 2-center problem in a simple polygon

被引：7

作者：

Oh, Eunjin ^{[1
]}

De Carufel, Jean-Lou ^{[2
]}

Ahn, Hee-Kap ^{[1
]}

机构：

[1] Pohang Univ Sci & Technol, Dept Comp Sci & Engn, Pohang, South Korea

[2] Univ Ottawa, Ottawa, ON, Canada

来源：

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS | 2018年 / 74卷

关键词：

Simple polygons; k-center problem; Geodesic distance; LINEAR-TIME ALGORITHMS;

D O I：

10.1016/j.comgeo.2018.02.008

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

In the geodesic 2-center problem in a simple polygon with n vertices, we find a set S of two points in the polygon that minimizes the maximum geodesic distance from any point of the polygon to its closest point in S. In this paper, we present an O (n(2) log(2) n)-time algorithm for this problem using O (n) space. (C) 2018 Elsevier B.V. All rights reserved.

引用

页码：21 / 37

页数：17

共 19 条

[1] A Linear-Time Algorithm for the Geodesic Center of a Simple Polygon [J].

Ahn, Hee-Kap ;

Barba, Luis ;

Bose, Prosenjit ;

De Carufel, Jean-Lou ;

Korman, Matias ;

Oh, Eunjin .

DISCRETE & COMPUTATIONAL GEOMETRY, 2016, 56 (04) :836-859

[2] THE FURTHEST-SITE GEODESIC VORONOI DIAGRAM [J].

ARONOV, B ;

FORTUNE, S ;

WILFONG, G .

DISCRETE & COMPUTATIONAL GEOMETRY, 1993, 9 (03) :217-255

[3]

Asano Tetsuo, 1985, SOCS8532 MCGIL U

[4] GEODESIC DISKS AND CLUSTERING IN A SIMPLE POLYGON [J].

Borgelt, Magdalene G. ;

Van Kreveld, Marc ;

Luo, Jun .

INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS, 2011, 21 (06) :595-608

[5] More planar two-center algorithms [J].

Chan, TM .

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 1999, 13 (03) :189-198

[6] PARALLEL MERGE SORT [J].

COLE, R .

SIAM JOURNAL ON COMPUTING, 1988, 17 (04) :770-785

[7]

Feder T., 1988, Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, P434, DOI 10.1145/62212.62255

[8] LINEAR-TIME ALGORITHMS FOR VISIBILITY AND SHORTEST-PATH PROBLEMS INSIDE TRIANGULATED SIMPLE POLYGONS [J].

GUIBAS, L ;

HERSHBERGER, J ;

LEVEN, D ;

SHARIR, M ;

TARJAN, RE .

ALGORITHMICA, 1987, 2 (02) :209-233

[9] OPTIMAL SHORTEST-PATH QUERIES IN A SIMPLE POLYGON [J].

GUIBAS, LJ ;

HERSHBERGER, J .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1989, 39 (02) :126-152

[10] THE SLAB DIVIDING APPROACH TO SOLVE THE EUCLIDEAN P-CENTER PROBLEM [J].

HWANG, RZ ;

LEE, RCT ;

CHANG, RC .

ALGORITHMICA, 1993, 9 (01) :1-22

← 1 2 →