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 条
  • [41] EXPERIMENTAL EVIDENCE CONCERNING LAW OF RECTILINEAR DIAMETER
    CORNFELD, AB
    CARR, HY
    PHYSICAL REVIEW LETTERS, 1972, 29 (01) : 28 - &
  • [42] Liquid-vapor rectilinear diameter revisited
    Garrabos, Y.
    Lecoutre, C.
    Marre, S.
    Beysens, D.
    Hahn, I.
    PHYSICAL REVIEW E, 2018, 97 (02)
  • [43] Realistic roofs without local minimum edges over a rectilinear polygon
    Yoon, Sang Duk
    Ahn, Hee-Kap
    Sherette, Jessica
    THEORETICAL COMPUTER SCIENCE, 2017, 675 : 15 - 26
  • [44] An algorithm for converting the contour of a 2D workpiece into a rectilinear polygon
    Wu, MC
    Wang, JT
    COMPUTERS IN INDUSTRY, 1996, 29 (03) : 197 - 208
  • [45] An Optimal Algorithm for Minimum-Link Rectilinear Paths in Triangulated Rectilinear Domains
    Joseph S. B. Mitchell
    Valentin Polishchuk
    Mikko Sysikaski
    Haitao Wang
    Algorithmica, 2019, 81 : 289 - 316
  • [46] An Optimal Algorithm for Minimum-Link Rectilinear Paths in Triangulated Rectilinear Domains
    Mitchell, Joseph S. B.
    Polishchuk, Valentin
    Sysikaski, Mikko
    Wang, Haitao
    AUTOMATA, LANGUAGES, AND PROGRAMMING, PT I, 2015, 9134 : 947 - 959
  • [47] An Optimal Algorithm for Minimum-Link Rectilinear Paths in Triangulated Rectilinear Domains
    Mitchell, Joseph S. B.
    Polishchuk, Valentin
    Sysikaski, Mikko
    Wang, Haitao
    ALGORITHMICA, 2019, 81 (01) : 289 - 316
  • [48] LINK LENGTH OF RECTILINEAR HAMILTONIAN TOURS IN GRIDS
    KRANAKIS, E
    KRIZANC, D
    MEETENS, L
    ARS COMBINATORIA, 1994, 38 : 177 - 192
  • [49] Computing the Newton Polygon of the Implicit Equation
    Emiris I.Z.
    Konaxis C.
    Palios L.
    Mathematics in Computer Science, 2010, 4 (1) : 25 - 44
  • [50] Computing the center of area of a convex polygon
    Brab, P
    Heinrich-Litan, L
    Morin, P
    INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS, 2003, 13 (05) : 439 - 445
12345