I/O-efficient algorithms for computing planar geometric spanners

被引：2
|
作者：
Maheshwari, Anil [2 ]
Smid, Michiel [2 ]
Zeh, Norbert [1 ]
机构：
[1] Fac Comp Sci, Halifax, NS B3H 1W5, Canada
[2] Carleton Univ, Sch Comp Sci, Ottawa, ON K1S 5B6, Canada
来源：
COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS | 2008年 / 40卷 / 03期
基金：
加拿大创新基金会;
关键词：
external-memory algorithms; computational geometry; geometric spanners; shortest paths;
D O I：
10.1016/j.comgeo.2007.07.007
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
We present I/O-efficient algorithms for computing planar Steiner spanners for point sets and sets of polygonal obstacles in the plane. (c) 2007 Elsevier B.V. All rights reserved.
引用
收藏
页码：252 / 271
页数：20
相关论文
共 33 条
  • [21] Optimal algorithms for computing the minimum distance between two finite planar sets
    Toussaint, Godfried T.
    Bhattacharya, Binay K.
    PATTERN RECOGNITION LETTERS, 1983, 2 (02) : 79 - 82
  • [22] Efficient algorithms for computing a complete visibility region in three-dimensional space
    Kim, DS
    Yoo, KH
    Chwa, KY
    Shin, SY
    ALGORITHMICA, 1998, 20 (02) : 201 - 225
  • [23] Efficient algorithms for computing one or two discrete centers hitting a set of line segments
    He, Xiaozhou
    Liu, Zhihui
    Su, Bing
    Xu, Yinfeng
    Zheng, Feifeng
    Zhu, Binhai
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2019, 37 (04) : 1408 - 1423
  • [24] Efficient algorithms for computing one or two discrete centers hitting a set of line segments
    Xiaozhou He
    Zhihui Liu
    Bing Su
    Yinfeng Xu
    Feifeng Zheng
    Binhai Zhu
    Journal of Combinatorial Optimization, 2019, 37 : 1408 - 1423
  • [25] Efficient burst scheduling algorithms in optical burst-switched networks using geometric techniques
    Xu, JH
    Qiao, CM
    Li, JK
    Xu, G
    IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS, 2004, 22 (09) : 1796 - 1811
  • [26] Efficient geometric algorithms for workpiece orientation in 4- and 5-axis NC machining
    Gupta, P
    Janardan, R
    Majhi, J
    Woo, T
    COMPUTER-AIDED DESIGN, 1996, 28 (08) : 577 - 587
  • [27] An I/O Efficient Algorithm for Minimum Spanning Trees
    Bhushan, Alka
    Sajith, Gopalan
    COMBINATORIAL OPTIMIZATION AND APPLICATIONS, (COCOA 2015), 2015, 9486 : 499 - 509
  • [28] DESIGNING EFFICIENT GEOMETRIC SEARCH ALGORITHMS USING PERSISTENT BINARY-BINARY SEARCH-TREES
    TAN, XH
    HIRATA, T
    INAGAKI, Y
    IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, 1994, E77A (04) : 601 - 607
  • [29] Space-efficient algorithms for computing the convex hull of a simple polygonal line in linear time
    Brönnimann, H
    Chan, TM
    COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2006, 34 (02): : 75 - 82
  • [30] Simple O(n log2 n) Algorithms for the Planar 2-Center Problem
    Tan, Xuehou
    Jiang, Bo
    COMPUTING AND COMBINATORICS, COCOON 2017, 2017, 10392 : 481 - 491
1234