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

スポンサーリンク

概要

• 論文の詳細を見る

• 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.

• 2010-03-05

著者

• OKAMOTO Yoshio

  Graduate School of Infomation Science and Engineering, Tokyo Institute of Technology

• BAE Sang

  Department of Computer Science and Engineering, POSTECH

• KORMAN Matias

  Computer Science Department, Universite Libre de Bruxelles, Belgium

• Korman Matias

  Computer Science Department Universite Libre De Bruxelles Belgium

• Okamoto Yoshio

  Graduate School Of Information Science And Engineering Tokyo Institute Of Technology

• Bae Sang

  Department Of Computer Science And Engineering Postech

• Bae Sang

  Department Of Chemical Engineering Pohang University Of Science And Technology

関連論文

• Adaptive Algorithms for Planar Convex Hull Problems
• Bipartite powers of interval bigraphs
• On the geodesic diameter in polygonal domains (コンピュテーション)
• The Induction of Heme Oxygenase-1 by Exogenous Nitric Oxide in ex vivo Normal Human Skin
• Unusual Erythemas with Eosinophilia, Caused by H_2-Blocker Famotidine in a Male Patient with Glioblastoma
• Template-free Hydrothermal Synthesis of High Surface Area Nitrogen-doped Titania Photocatalyst Active under Visible Light
• Hardness results and an exact exponential algorithm for the spanning tree congestion problem (コンピュテーション)
• In situ expreession of interleukin-4,-5 and -6 in Peyer's patch from ovalbumin-sensitized BALB/c mice after oral challenge
• The Inhibitory Effect of Anti-Adhesion Molecule Antibodies on Eosinophil Infiltration in Cutaneous Late Phase Response in Balb/c Mice Sensitized with Ovalbumin (OVA)
• Hardness results and an exact exponential algorithm for the spanning tree congestion problem (コンピュテーション)
• On Linear-Sized Farthest-Color Voronoi Diagrams
• The roles of P-and E-selectins and P-selectin glycoprotein ligand-1 in primary and metastatic mouse melanomas

もっと見る 閉じる

スポンサーリンク