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 条
  • [1] I/O-Efficient Algorithms for Graphs of Bounded Treewidth
    Maheshwari, Anil
    Zeh, Norbert
    ALGORITHMICA, 2009, 54 (03) : 413 - 469
  • [2] I/O-Efficient Algorithms for Graphs of Bounded Treewidth
    Anil Maheshwari
    Norbert Zeh
    Algorithmica, 2009, 54 : 413 - 469
  • [3] I/O-Efficient Path Traversal in Succinct Planar Graphs
    Dillabaugh, Craig
    He, Meng
    Maheshwari, Anil
    Zeh, Norbert
    ALGORITHMICA, 2017, 77 (03) : 714 - 755
  • [4] I/O-Efficient Path Traversal in Succinct Planar Graphs
    Craig Dillabaugh
    Meng He
    Anil Maheshwari
    Norbert Zeh
    Algorithmica, 2017, 77 : 714 - 755
  • [5] I/O-efficient well-separated pair decomposition and applications
    Govindarajan, Sathish
    Lukovszki, Tamas
    Maheshwari, Anil
    Zeh, Norbert
    ALGORITHMICA, 2006, 45 (04) : 585 - 614
  • [6] Lower bounds for computing geometric spanners and approximate shortest paths
    Chen, DZ
    Das, G
    Smid, H
    DISCRETE APPLIED MATHEMATICS, 2001, 110 (2-3) : 151 - 167
  • [7] Fast greedy algorithms for constructing sparse geometric spanners
    Gudmundsson, J
    Levcopoulos, C
    Narasimhan, G
    SIAM JOURNAL ON COMPUTING, 2002, 31 (05) : 1479 - 1500
  • [8] I/O-Efficient Well-Separated Pair Decomposition and Applications
    Sathish Govindarajan
    Tamas Lukovszki
    Anil Maheshwari
    Norbert Zeh
    Algorithmica, 2006, 45 : 585 - 614
  • [9] I/O-efficient multilevel graph partitioning algorithm for massive graph data
    Her, JH
    Ramakrishna, RS
    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, 2004, E87D (07) : 1789 - 1794
  • [10] Dynamic algorithms for geometric spanners of small diameter: Randomized solutions
    Arya, S
    Mount, DM
    Smid, M
    COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 1999, 13 (02): : 91 - 107
1234