Local properties of geometric graphs

被引:0
作者
Cardinal, Jean [1 ]
Collette, Sebastien [1 ]
Langerman, Stefan [1 ]
机构
[1] Univ Libre Bruxelles, Dept Comp Sci, B-1050 Brussels, Belgium
来源
COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS | 2008年 / 39卷 / 01期
关键词
geometric graphs; region-counting distances; spanning ratio;
D O I
10.1016/j.comgeo.2007.05.011
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
We propose a definition of locality for properties of geometric graphs. We measure the local density of graphs using region-counting distances between pairs of vertices, and we use this density to define local properties of classes of graphs. We illustrate locality by introducing the local diameter of geometric graphs: we define it as the upper bound on the size of the shortest path between any pair of vertices, expressed as a function of the density of the graph around these vertices. We determine the local diameter of several well-studied graphs such as Theta-graphs, Ordered Theta-graphs and Skip List Spanners. We also show that various operations, such as path and point queries using geometric graphs as data structures, have complexities which can be expressed as local properties. (c) 2007 Elsevier B.V. All rights reserved.
引用
收藏
页码:55 / 64
页数:10
相关论文
共 19 条
[1]  
[Anonymous], P 2 ACM S COMP GEOM
[2]  
[Anonymous], 1991, P 3 CANADIAN C COMPU
[3]  
Arya S., 1994, Proceedings. 35th Annual Symposium on Foundations of Computer Science (Cat. No.94CH35717), P703, DOI 10.1109/SFCS.1994.365722
[4]  
BOAS PV, 1990, HDB THEORETICAL COMP, VA
[5]  
BOSE P, 2002, P CAN C COMP GEOM CC, P17
[6]   DESIGN AND ANALYSIS OF A DATA STRUCTURE FOR REPRESENTING SORTED LISTS [J].
BROWN, MR ;
TARJAN, RE .
SIAM JOURNAL ON COMPUTING, 1980, 9 (03) :594-614
[7]  
CARDINAL J, 2005, P CAN C COMP GEOM CC, P278
[8]  
CARDINAL J, 2005, P 21 EUR WORKSH COMP
[9]  
Clarkson Ken, 1987, PROC 19 STOC, P56
[10]  
DEMAINE ED, 2002, P 14 CAN C COMP GEOM