An Optimal Algorithm for Minimum-Link Rectilinear Paths in Triangulated Rectilinear Domains

被引：3

作者：

Mitchell, Joseph S. B. ^{[1
]}

Polishchuk, Valentin ^{[2
]}

Sysikaski, Mikko ^{[3
]}

Wang, Haitao ^{[4
]}

机构：

[1] SUNY Stony Brook, Stony Brook, NY 11794 USA

[2] Linkoping Univ, Linkoping, Sweden

[3] Google, Zurich, Switzerland

[4] Utah State Univ, Logan, UT 84322 USA

来源：

ALGORITHMICA | 2019年 / 81卷 / 01期

基金：

美国国家科学基金会;

关键词：

SHORTEST PATHS; SEARCH; COMPLEXITY; OBSTACLES; POLYGONS; QUERIES; GRAPH;

D O I：

10.1007/s00453-018-0446-1

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

We present a new algorithm for finding minimum-link rectilinear paths among rectilinear obstacles in the plane. Given a triangulated rectilinear domain of h pairwise-disjoint rectilinear obstacles with a total of n vertices, our algorithm can find a minimum-link rectilinear path between any two points in O(n+hlogh) time. Further, within the same time our algorithm can build an O(n)-size data structure for any source point s, such that given any query point t, the number of edges of a minimum-link rectilinear path from s to t can be computed in O(logn) time and the actual path can be output in additional time linear in the number of the edges of the path. The previously best algorithms for the problems run in O(nlogn) time.

引用

页码：289 / 316

页数：28

共 39 条

[1] MINIMUM-LINK C-ORIENTED PATHS: SINGLE-SOURCE QUERIES [J].

Adegeest, John ;

Overmars, Mark ;

Snoeyink, Jack .

INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS, 1994, 4 (01) :39-51

[2] LOGARITHMIC-TIME LINK PATH QUERIES IN A SIMPLE POLYGON [J].

ARKIN, EM ;

MITCHELL, JSB ;

SURI, S .

INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS, 1995, 5 (04) :369-395

[3] TRIANGULATING DISJOINT JORDAN CHAINS [J].

Bar-Yehuda, Reuven ;

Chazelle, Bernard .

INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS, 1994, 4 (04) :475-481

[4] TRIANGULATING A SIMPLE POLYGON IN LINEAR TIME [J].

CHAZELLE, B .

DISCRETE & COMPUTATIONAL GEOMETRY, 1991, 6 (05) :485-524

[5] TRIANGULATION AND SHAPE-COMPLEXITY [J].

CHAZELLE, B ;

INCERPI, J .

ACM TRANSACTIONS ON GRAPHICS, 1984, 3 (02) :135-152

[6]

Chen D.Z., 2014, Proc. 30th Annual Symp. Comput. Geom, P406

[7]

Chen DZ, 2011, LECT NOTES COMPUT SC, V6942, P481, DOI 10.1007/978-3-642-23719-5_41

[8]

Cormen T. H., 2009, Introduction to algorithms, VThird

[9]

Das G., 1991, P 2 WORKSH ALG DAT S, P261

[10]

de Berg M., 1991, Computational Geometry: Theory and Applications, V1, P13, DOI 10.1016/0925-7721(91)90010-C

← 1 2 3 4 →