A NEW DATA STRUCTURE FOR SHORTEST-PATH QUERIES IN A SIMPLE POLYGON

被引：37

作者：

HERSHBERGER, J

机构：

[1] DEC Systems Research Center, Palo Alto, CA 94301

来源：

INFORMATION PROCESSING LETTERS | 1991年 / 38卷 / 05期

关键词：

COMPUTATIONAL GEOMETRY; DATA STRUCTURES; ALGORITHM DESIGN AND ANALYSIS; CONVEX HULL;

D O I：

10.1016/0020-0190(91)90064-O

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

This note describes a new data structure for answering shortest path queries inside a simple polygon. The new data structure has the same asymptotic performance as the previously known data structure (linear preprocessing after triangulation, logarithmic query time), but it is significantly less complicated.

引用

页码：231 / 235

页数：5

共 9 条

[1]

BHATTACHARYA B, 1986, SOCS861 MCGILL U SCH

[2]

CHAZELLE B, 1990, 31ST P ANN IEEE S F, P220

[3]

DRISCOLL J, 1986, 18TH P ANN ACM S THE, P109

[4] LINEAR-TIME ALGORITHMS FOR VISIBILITY AND SHORTEST-PATH PROBLEMS INSIDE TRIANGULATED SIMPLE POLYGONS [J].