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 条
  • [31] Combating I-O bottleneck using prefetching: model, algorithms, and ramifications
    Verma, Akshat
    Sen, Sandeep
    JOURNAL OF SUPERCOMPUTING, 2008, 45 (02) : 205 - 235
  • [32] Combating I-O bottleneck using prefetching: model, algorithms, and ramifications
    Akshat Verma
    Sandeep Sen
    The Journal of Supercomputing, 2008, 45 : 205 - 235
  • [33] VORONOI DIAGRAMS ON PLANAR GRAPHS, AND COMPUTING THE DIAMETER IN DETERMINISTIC (O)over-tilde(n5/3) TIME
    Gawrychowski, Pawel
    Kaplan, Haim
    Mozes, Shay
    Sharir, Micha
    Weimann, Oren
    SIAM JOURNAL ON COMPUTING, 2021, 50 (02) : 509 - 554
1234