Sigma-local graphs
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 (12) (2005) 101125]. We present two algorithms to construct such graphs, for any real number ?>1 ? > 1 and any set S of n  points. These algorithms run in time O(?dn+nlogn) O ( ? d n + n log n ) for sets in Rd R d and O(nlog3nloglogn+k) O ( n log 3 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(nlogO(1)n) O ( n log O ( 1 ) n ) . These algorithms can also be used to efficiently construct the corresponding graphs.
geometric graphs proximity graphs