| Abstract Sigma-Local Graphs (2008) | |||||||||||||||
Abstract | |||||||||||||||
| We introduce and analyze σ-local graphs, based on a definition of locality by Erickson [9]. 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. In R 2, we also present a preprocessing method to find the graph corresponding to any σ in linear time using O(n log O(1) n) space and preprocessing time. Algorithms to find the minimum or maximum σ such that the corresponding graph has properties such as connectivity, completeness, planarity, and no-isolated vertex are presented, with complexities in O(n log O(1) n). These algorithms can also be used to efficiently construct the corresponding graphs. 1 | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||