| Presentation | 2010-03-12 On the Geodesic Diameter in Polygonal Domains Sang Won BAE, Matias KORMAN, Yoshio OKAMOTO, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | 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. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | |
| Paper # | COMP2009-53 |
| Date of Issue |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 2010/3/5(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Theoretical Foundations of Computing (COMP) |
|---|---|
| Language | ENG |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | On the Geodesic Diameter in Polygonal Domains |
| Sub Title (in English) | |
| Keyword(1) | |
| 1st Author's Name | Sang Won BAE |
| 1st Author's Affiliation | Department of Computer Science and Engineering, POSTECH() |
| 2nd Author's Name | Matias KORMAN |
| 2nd Author's Affiliation | Computer Science Department, Universite Libre de Bruxelles, Belgium |
| 3rd Author's Name | Yoshio OKAMOTO |
| 3rd Author's Affiliation | Graduate School of Information Science and Engineering, Tokyo Institute of Technology |
| Date | 2010-03-12 |
| Paper # | COMP2009-53 |
| Volume (vol) | vol.109 |
| Number (no) | 465 |
| Page | pp.pp.- |
| #Pages | 8 |
| Date of Issue | |