2010-03-01
Sigma-local graphs
Publication
Publication
Journal of Discrete Algorithms , Volume 8 - Issue 1 p. 15- 23
We introduce and analyze σ-local graphs, based on a definition of locality by Erickson [J. Erickson, Local polyhedra and geometric graphs, Computational Geometry: Theory and Applications 31 (1-2) (2005) 101-125]. We present two algorithms to construct such graphs, for any real number σ > 1 and any set S of n points. These algorithms run in time O (σd n + n log n) for sets in Rd and O (n log3 n log log n + k) for sets in the plane, where k is the size of the output. For sets in the plane, algorithms to find the minimum or maximum σ such that the corresponding graph has properties such as connectivity, planarity, and no-isolated vertex are presented, with complexities in O (n logO (1) n). These algorithms can also be used to efficiently construct the corresponding graphs.
| Additional Metadata | |
|---|---|
| Geometric graphs, Proximity graphs | |
| dx.doi.org/10.1016/j.jda.2008.10.002 | |
| Journal of Discrete Algorithms | |
| Organisation | School of Computer Science |
|
Bose, P, Collette, S. (Sébastien), Langerman, S. (Stefan), Maheshwari, A, Morin, P, & Smid, M. (2010). Sigma-local graphs. Journal of Discrete Algorithms, 8(1), 15–23. doi:10.1016/j.jda.2008.10.002
|
|