کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
430628 | 688072 | 2010 | 9 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Sigma-local graphs Sigma-local graphs](/preview/png/430628.png)
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σ>1 and any set S of n points. These algorithms run in time O(σdn+nlogn)O(σdn+nlogn) for sets in RdRd and O(nlog3nloglogn+k)O(nlog3nloglogn+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(nlogO(1)n). These algorithms can also be used to efficiently construct the corresponding graphs.
Journal: Journal of Discrete Algorithms - Volume 8, Issue 1, March 2010, Pages 15–23