Sphere-of-influence graphs in normed spaces

DOI10.1007/978-3-319-78434-2_16MaRDI QIDQ1740485zbMATH OpenOpenAlexFDO

Authors Márton Naszódi, János Pach, Konrad J. Swanepoel

Publication date 30 April 2019

Full work available at URL https://arxiv.org/abs/1605.01872

zbMATH Keywords

Besicovitch covering theorempoint packing numberproximity graphsphere packings

Mathematics Subject Classification ID

Combinatorial aspects of packing and covering (05B40) Graph representations (geometric and intersection representations, etc.) (05C62) Structural characterization of families of graphs (05C75) Length, area, volume, other geometric measure theory (28A75)

Abstract: We show that any $k$-th closed sphere-of-influence graph in a $d$-dimensional normed space has a vertex of degree less than~$5^{d}k$, thus obtaining a common generalization of results of F"uredi and Loeb (1994) and Guibas, Pach and Sharir (1994).

Recommendations

• Sphere-of-influence graphs using the sup-norm
• Sphere of influence graphs in general metric spaces
• scientific article; zbMATH DE number 739019
• Sphere of influence graphs and the \(L_{\infty}\)-metric
• Abstract sphere-of-influence graphs
• scientific article; zbMATH DE number 3915114
• Publication:4862245
• On a sphere of influence graph in a one-dimensional space
• scientific article; zbMATH DE number 1228440
• Publication:4489176

Cited in

(4)

• Abstract sphere-of-influence graphs
• Sphere of influence graphs and the \(L_{\infty}\)-metric
• scientific article; zbMATH DE number 739019 (Why is no real title available?)
• Sphere-of-influence graphs on a sphere.

This page was built for publication: Sphere-of-influence graphs in normed spaces

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1740485)