Local Construction of Spanners in the 3-D Space

被引:0
作者
Kanj, Iyad A. [1 ]
Xia, Ge [2 ,3 ]
Zhang, Fenghui
机构
[1] Depaul Univ, Sch CTI, 243 S Wabash Ave, Chicago, IL 60604 USA
[2] Lafayette Coll, Dept Comp Sci, Easton, PA 18042 USA
[3] Google Seattle, 601 N 34th St, Seattle, WA 98103 USA
来源
DISTRIBUTED COMPUTING IN SENSOR SYSTEMS, PROCEEDINGS | 2009年 / 5516卷
关键词
GRAPHS;
D O I
暂无
中图分类号
TP3 [计算技术、计算机技术];
学科分类号
0812 ;
摘要
In this paper we present local distributed algorithms for constructing spanners in wireless sensor networks modeled as unit ball graphs (shortly UBGs) and quasi-unit ball graphs (shortly quasi-UBGs), in the 3-dimensional Euclidean space. Our first contribution is a local distributed algorithm that, given a UBG U and a parameter alpha < pi/3, constructs a sparse spanner of U with stretch factor 1/(1 - 2 sin (alpha/2)), improving the previous upper bound of 1/(1 - alpha) by Althofer et al. which is applicable only when alpha < 1/(1 + 2 root-2) < pi/3. The second contribution of this paper is in presenting the first local distributed algorithm for the construction of bounded-degree lightweight spanners of UBGs and quasi-UBGs. The simulation results we obtained show that, empirically, the weight of the spanners, the stretch factor and locality of the algorithms, are much better than the theoretical upper bounds proved in this paper.
引用
收藏
页码:315 / +
页数:2
相关论文
共 50 条
  • [31] 3D Object Classification via Part Graphs
    Teich, Florian
    Lueddecke, Timo
    Woergoetter, Florentin
    VISAPP: PROCEEDINGS OF THE 16TH INTERNATIONAL JOINT CONFERENCE ON COMPUTER VISION, IMAGING AND COMPUTER GRAPHICS THEORY AND APPLICATIONS - VOL. 5: VISAPP, 2021, : 417 - 426
  • [32] Medial Spectral Coordinates for 3D Shape Analysis
    Rezanejad, Morteza
    Khodadad, Mohammad
    Mahyar, Hamidreza
    Lombaert, Herve
    Gruninger, Michael
    Walther, Dirk
    Siddiqi, Kaleem
    2022 IEEE/CVF CONFERENCE ON COMPUTER VISION AND PATTERN RECOGNITION (CVPR 2022), 2022, : 2676 - 2686
  • [33] A Supervised Approach to 3D Structural Classification of Proteins
    Cantoni, Virginio
    Ferone, Alessio
    Petrosino, Alfredo
    di Baja, Gabriella Sanniti
    NEW TRENDS IN IMAGE ANALYSIS AND PROCESSING - ICIAP 2013, 2013, 8158 : 326 - 335
  • [34] Existence, characterization and stability of Pansu spheres in sub-Riemannian 3-space forms
    Hurtado, Ana
    Rosales, Cesar
    CALCULUS OF VARIATIONS AND PARTIAL DIFFERENTIAL EQUATIONS, 2015, 54 (03) : 3183 - 3227
  • [35] The space of embedded minimal surfaces of fixed genus in a 3-manifold V; Fixed genus
    Colding, Tobias H.
    Minicozzi, William P., II
    ANNALS OF MATHEMATICS, 2015, 181 (01) : 1 - 153
  • [36] Aesthetics and comprehension of curved 3D graphs in Virtual Reality
    Drogemuller, Adam
    Cunningham, Andrew
    Walsh, James
    Baumeister, James
    Smith, Ross T.
    Thomas, Bruce H.
    JOURNAL OF COMPUTER LANGUAGES, 2023, 75
  • [37] 3D MESH SEGMENTATION OF HISTORIC BUILDINGS FOR ARCHITECTURAL SURVEYS
    Javier Herraez, Borja
    Vendrell, Eduardo
    VIRTUAL ARCHAEOLOGY REVIEW, 2018, 9 (18): : 66 - 76
  • [38] Monocular Semantic Mapping Based on 3D Cuboids Tracking
    Ji, Xingwu
    Gong, Zheng
    Miao, Ruihang
    Xue, Wuyang
    Ying, Rendong
    2021 IEEE INTERNATIONAL SYMPOSIUM ON CIRCUITS AND SYSTEMS (ISCAS), 2021,
  • [39] A construction of a partial difference set in the extraspecial groups of order p3 with exponent p2
    Swartz, Eric
    DESIGNS CODES AND CRYPTOGRAPHY, 2015, 75 (02) : 237 - 242
  • [40] Stable Maps from #n(S1xS2)to the Euclidean 3-Space
    Huamani, N. B.
    de Jesus, C. Mendes
    Palacios, J.
    MEDITERRANEAN JOURNAL OF MATHEMATICS, 2024, 21 (03)