On the geodesic diameter in polygonal domains (コンピュテーション) On the Geodesic Diameter in Polygonal Domains

 Bae Sang Won BAE Sang Won
 Department of Computer Science and Engineering, POSTECH

 Korman Matias KORMAN Matias
 Computer Science Department, Universite Libre de Bruxelles

 Okamoto Yoshio OKAMOTO Yoshio
 Graduate School of Information Science and Engineering, Tokyo Institute of Technology
Search this Article
Author(s)

 Bae Sang Won BAE Sang Won
 Department of Computer Science and Engineering, POSTECH

 Korman Matias KORMAN Matias
 Computer Science Department, Universite Libre de Bruxelles

 Okamoto Yoshio OKAMOTO Yoshio
 Graduate School of Information Science and Engineering, Tokyo Institute of Technology
Abstract
This paper studies the geodesic diameter in polygonal domains having h holes and n corners. For simple polygons (i.e., h=0), it is known that the geodesic diameter is determined by a pair of corners of a given polygon and can be computed in linear time. For general polygonal domains with h〓1, however, there was no known algorithm for computing the geodesic diameter prior to this paper. We present the first algorithms that compute the geodesic diameter of a given polygonal domain in either O(n^<7.73>) or O(n^7(log n+h)) time. The algorithms are based on our new geometric observations, a part of which states as follows: the geodesic diameter of a polygonal domain can be determined by two points in its interior, and in that case there are at least five shortest paths between the two points. This article is a technical report without peer review, and its polished version will be published elsewhere.
Journal

 IEICE technical report

IEICE technical report 109(465), 2532, 20100305
The Institute of Electronics, Information and Communication Engineers
References: 18

1
 Star unfolding of a polytope with applications

AGARWAL P. K.
SIAM J. Comput. 26(6), 16891713, 1997
Cited by (1)

2
 The furthestsite geodesic Voronoi diagram

ARONOV B.
Discrete Comput. Geom. 9, 217255, 1993
Cited by (1)

3
 <no title>

ASANO T.
Computing the geodesic center of a simple polygon, 1985
Cited by (1)

4
 The geodesic farthestsite Voronoi diagram in a polygonal domain with holes

BAE S. W.
Proc. 25th Annu. Sympos. Comput. Geom. (SoCG), 2009, 198207, 2009
Cited by (1)

5
 Querying two boundary points for shortest paths in a polygonal domain

BAE S. W.
Proc. 20th Annu. Internat. Sympos. Algo. Comput. (ISAAC), 2009, 10541063, 2009
Cited by (1)

6
 A theorem on polygon cutting with applications

CHAZELLE B.
Proc. 23rd Annu. Sympos. Found. Comput. Sci. (FOCS), 1982, 339349, 1982
Cited by (1)

7
 Twopoint Euclidean shortest path queries in the plane

CHIANG Y.J.
Proc. 10th ACMSIAM Sympos. Discrete Algorithms (SODA), 1999, 215224, 1999
Cited by (1)

8
 Shortest path problems on a polyhedral surface

COOK A. F. IV
Proc. 11th Internat. Sympos. Algo. Data Struct. (WADS), 2009, 156167, 2009
Cited by (1)

9
 Shortest path queries in polygonal domains

GUO H.
Proc. 4th Internat. Conf. Algo. Aspects Info. Management (AAIM), 2008, 200211, 2008
Cited by (1)

10
 Shortest paths and networks

MITCHELL J. S. B.
Handbook of Discrete and Computational Geometry, 607641, 2004
Cited by (1)

11
 Computing the geodesic diameter of a 3polytope

O'ROURKE J.
Proc. 5th Annu. Sympos. Comput. Geom. (SoCG), 1989, 370379, 1989
Cited by (1)

12
 Polygons

O'ROURKE J.
Handbook of Discrete and Computational Geometry, 583606, 2004
Cited by (1)

13
 Computing the geodesic center of a simple polygon

POLLACK R.
Discrete Comput. Geom. 4(6), 611626, 1989
Cited by (1)

14
 The allgeodesicfurthest neighbors problem for simple polygons

SURI S.
Proc. 3rd Annu. Sympos. Comput. Geom. (SoCG), 1987 64, 1987
Cited by (1)

15
 Optimal shortest path queries in a simple polygon

GUIBAS L.
J. Comput. Syst. Sci. 39(2), 126152, 1989
Cited by (3)

16
 Matrix searching with the shortest path metric

HERSHBERGER J.
SIAM J. Comput. 26(6), 16121634, 1997
Cited by (2)

17
 An optimal algorithm for Euclidean shortest paths in the plane

HERSHBERGER J.
SIAM J. Comput. 28(6), 22152256, 1999
Cited by (1)

18
 Shortest paths among obstacles in the plane

MITCHELL J. S. B.
Internat. J. Comput. Geom. Appl. 6(3), 309331, 1996
Cited by (1)