An optimal algorithm for the rectilinear link center of a rectilinear polygon

被引：7
|
作者：
Nilsson, BJ
Schuierer, S
机构：
[1] LUND UNIV, DEPT COMP SCI, S-22100 LUND, SWEDEN
[2] UNIV FREIBURG, INST INFORMAT, D-79104 FREIBURG, GERMANY
来源：
COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS | 1996年 / 6卷 / 03期
关键词：
This work was supported by the Deutsche Forschungs Gemeinschaft under Grant No. Ot 64/5--4;
D O I：
10.1016/0925-7721(95)00026-7
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
The link distance between two points in a polygon P is defined as the minimum number of line segments inside P needed to connect the two points. The link center of a polygon P is the set of points in P which the maximum link distance to all points in P. The problem of finding the link center of a simple polygon with n edges has been studied extensively in recent years. Several O(n log n) time algorithms have been given for this problem. We consider the rectilinear case of this problem and give a linear time algorithm to compute the rectilinear link center of a simple rectilinear polygon.
引用
收藏
页码：169 / 194
页数：26
相关论文
共 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] 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
  • [4] COMPUTING THE RECTILINEAR LINK DIAMETER OF A POLYGON
    NILSSON, BJ
    SCHUIERER, S
    LECTURE NOTES IN COMPUTER SCIENCE, 1991, 553 : 203 - 215
  • [5] 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
  • [6] 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
  • [7] 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
  • [8] 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
  • [9] AN OPTIMAL APPROXIMATION ALGORITHM FOR THE RECTILINEAR M-CENTER PROBLEM
    KO, MT
    LEE, RCT
    CHANG, JS
    ALGORITHMICA, 1990, 5 (03) : 341 - 352
  • [10] 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
12345