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 (1–2) (2005) 101–125]. We present two algorithms to construct such graphs, for any real number σ > 1 and an...

Full description

Saved in:
Bibliographic Details
Published in:Journal of discrete algorithms (Amsterdam, Netherlands) Netherlands), 2010-03, Vol.8 (1), p.15-23
Main Authors: Bose, Prosenjit, Collette, Sébastien, Langerman, Stefan, Maheshwari, Anil, Morin, Pat, Smid, Michiel
Format: Article
Language:English
Subjects:
Geometric graphs
Proximity graphs
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 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. 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 log O ( 1 ) n ) . These algorithms can also be used to efficiently construct the corresponding graphs.
ISSN:1570-8667
1570-8675
DOI:10.1016/j.jda.2008.10.002