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

Search this Article

Author(s)

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), 25-32, 2010-03-05

    The Institute of Electronics, Information and Communication Engineers

References:  18

Codes

  • NII Article ID (NAID)
    110008000709
  • NII NACSIS-CAT ID (NCID)
    AN10013152
  • Text Lang
    ENG
  • Article Type
    ART
  • ISSN
    09135685
  • NDL Article ID
    10649320
  • NDL Source Classification
    ZN33(科学技術--電気工学・電気機械工業--電子工学・電気通信)
  • NDL Call No.
    Z16-940
  • Data Source
    CJP  NDL  NII-ELS 
Page Top