| Abstract Sigma-Local Graphs (2008) | |||||||||||||||
Abstract | |||||||||||||||
| We introduce and analyze σ-local graphs, based on a definition of locality by Erickson [11]. 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 R d and O(n log 3 n log log n + k) for sets in the plane, where k is the size of the output. 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 n log O(1) n. These algorithms can also be used to efficiently construct the corresponding graphs. 1 | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||