COMPUTING THE RECTILINEAR LINK DIAMETER OF A POLYGON

被引：0
|
作者：
NILSSON, BJ [1 ]
SCHUIERER, S [1 ]
机构：
[1] UNIV FREIBURG,INST INFORMAT,W-7800 FREIBURG,GERMANY
来源：
LECTURE NOTES IN COMPUTER SCIENCE | 1991年 / 553卷
关键词：
D O I：
暂无
中图分类号：
TP31 [计算机软件];
学科分类号：
081202 ; 0835 ;
摘要：
The problem of finding the diameter of a simple polygon has been studied extensively in recent years. O(n log n) time upper bounds have been given for computing the geodesic diameter and the link diameter for a polygon. We consider the rectilinear case of this problem and give a linear time algorithm to compute the rectilinear link diameter of a simple rectilinear polygon. To our knowledge this is the first optimal algorithm for the diameter problem of non-trivial classes of polygons.
引用
收藏
页码：203 / 215
页数：13
相关论文
共 50 条
  • [21] An optimal data structure for shortest rectilinear path queries in a simple rectilinear polygon
    Schuierer, S
    INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS, 1996, 6 (02) : 205 - 225
  • [22] Generating Realistic Roofs over a Rectilinear Polygon
    Ahn, Hee-Kap
    Bae, Sang Won
    Knauer, Christian
    Lee, Mira
    Shin, Chan-Su
    Vigneron, Antoine
    ALGORITHMS AND COMPUTATION, 2011, 7074 : 60 - +
  • [23] The smallest pair of noncrossing paths in a rectilinear polygon
    Yang, CD
    Lee, DT
    Wong, CK
    IEEE TRANSACTIONS ON COMPUTERS, 1997, 46 (08) : 930 - 941
  • [24] THE HISTORY OF THE RECTILINEAR DIAMETER LAW
    Reif-Acherman, Simon
    QUIMICA NOVA, 2010, 33 (09): : 2003 - 2010
  • [25] On the rectilinear diameter for argon.
    Mathias, E
    Onnes, HK
    Crommelin, CA
    PROCEEDINGS OF THE KONINKLIJKE AKADEMIE VAN WETENSCHAPPEN TE AMSTERDAM, 1912, 15 : 667 - 673
  • [26] On the rectilinear diameter for argon.
    Mathias, E
    Onnes, HK
    Crommelin, CA
    PROCEEDINGS OF THE KONINKLIJKE AKADEMIE VAN WETENSCHAPPEN TE AMSTERDAM, 1913, 15 : 960 - 965
  • [27] AN O(N LOG N) ALGORITHM FOR COMPUTING A LINK CENTER IN A SIMPLE POLYGON
    DJIDJEV, HN
    LINGAS, A
    SACK, JR
    LECTURE NOTES IN COMPUTER SCIENCE, 1989, 349 : 96 - 107
  • [28] The nature of the rectilinear diameter singularity
    Kulinskii, V. L.
    Malomuzh, N. P.
    PHYSICA A-STATISTICAL MECHANICS AND ITS APPLICATIONS, 2009, 388 (05) : 621 - 627
  • [29] Computing the L1 Geodesic Diameter and Center of a Simple Polygon in Linear Time
    Bae, Sang Won
    Korman, Matias
    Okamoto, Yoshio
    Wang, Haitao
    LATIN 2014: THEORETICAL INFORMATICS, 2014, 8392 : 120 - 131
  • [30] Computing the L1 geodesic diameter and center of a simple polygon in linear time
    Bae, Sang Won
    Korman, Matias
    Okamoto, Yoshio
    Wang, Haitao
    COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2015, 48 (06): : 495 - 505
12345