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 条
  • [1] Optimal algorithm for the rectilinear link center of a rectilinear polygon
    Comput Geom Theory Appl, 3 (169):
  • [2] AN OPTIMAL ALGORITHM FOR THE RECTILINEAR LINK CENTER OF A RECTILINEAR POLYGON
    NILSSON, BJ
    SCHUIERER, S
    LECTURE NOTES IN COMPUTER SCIENCE, 1991, 519 : 249 - 260
  • [3] An optimal algorithm for the rectilinear link center of a rectilinear polygon
    Nilsson, BJ
    Schuierer, S
    COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 1996, 6 (03): : 169 - 194
  • [4] Settling the bound on the rectilinear link radius of a simple rectilinear polygon
    Katz, Matthew J.
    Morgenstern, Gila
    INFORMATION PROCESSING LETTERS, 2011, 111 (03) : 103 - 106
  • [5] Computing a maxian point of a simple rectilinear polygon
    Wang, D. P.
    OPERATIONS RESEARCH LETTERS, 2007, 35 (01) : 54 - 60
  • [6] COMPUTING A MEDIAN POINT OF A SIMPLE RECTILINEAR POLYGON
    CHEPOI, V
    DRAGAN, F
    INFORMATION PROCESSING LETTERS, 1994, 49 (06) : 281 - 285
  • [7] Rectilinear link diameter and radius in a rectilinear polygonal domain
    Arseneva, Elena
    Chiu, Man-Kwun
    Korman, Matias
    Markovic, Aleksandar
    Okamoto, Yoshio
    Ooms, Aurelien
    Renssen, Andre van
    Roeloffzen, Marcel
    COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2021, 92
  • [8] COMPUTING THE LINK CENTER OF A SIMPLE POLYGON
    LENHART, W
    POLLACK, R
    SACK, J
    SEIDEL, R
    SHARIR, M
    SURI, S
    TOUSSAINT, G
    WHITESIDES, S
    YAP, C
    DISCRETE & COMPUTATIONAL GEOMETRY, 1988, 3 (03) : 281 - 293
  • [9] COMPUTING THE EXTERNAL GEODESIC DIAMETER OF A SIMPLE POLYGON
    SAMUEL, D
    TOUSSAINT, GT
    COMPUTING, 1990, 44 (01) : 1 - 19
  • [10] Computing optimal diameter-bounded polygon partitions
    Damiani, M
    Pemmaraju, SV
    ALGORITHMICA, 2004, 40 (01) : 1 - 14
12345