Avoiding Distances
Abstract
Given a finite planar point set X={x1,…,xn}, let a1<a2< ⋯ < as denote the s ≤ n choose 2 different (Euclidean) distances between points in X. The aim is to retain as many of the points as possible such that certain imposed inter-pair distances are avoided. For example, we show that: (A) Given a set X of n points in the plane, an independent set of size $0.2293 n$ in the unit distance graph determined by X can be found in O(n2) time. For any fixed k ∈ N there exists a constant ck>0 such that for any set X of n points in the plane, and set D of size k, there exists a subset X' ⊆ X of size |X'| ≥ ck |X| in which no pair of points is at some distance in D (we say that X' avoids distances in D). Such a set can be found efficiently. (B) (i) There is a subset of X of size n/2 that avoids the maximum distance; this bound cannot be improved. (ii) There is a subset of X of size 8n/47 that avoids both the minimum and maximum distance; on the other hand, there exists X such that at most 5n/16 points can be retained with this property. (iii) There is a subset of X of size n/7 whose diameter is at most half the original diameter; on the other hand, there exists X such that at most n/6 points can be retained with this property. (C) (i) For any ε>0, a (1−ε)-approximation for \textsc{MIS} in the minimum distance graph of n points in the plane can be found in 2O(1/ε) nO(1) time. (ii) Given a set X of n points in the plane, a maximum independent set in the graph of diameters can be computed in O(n2) time. The techniques used to handle the planar case can be extended to Rd for any fixed dimension d.
Related
BibTeX
@misc{dumitrescu2026avoiding,
title = {{Avoiding Distances}},
author = {Adrian Dumitrescu and Zsolt Lángi},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.24803},
eprint = {2610.24803},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.24803},
}
RIS
TY - UNPB
TI - Avoiding Distances
AU - Adrian Dumitrescu
AU - Zsolt Lángi
PY - 2026
DA - 2026/10/17
PB - arXiv
DO - 10.48550/arxiv.2610.24803
UR - https://arxiv.org/abs/2610.24803
AB - Given a finite planar point set X={x_1,…,x_n}, let a_1<a_2< ⋯ < a_s denote the s ≤ n choose 2 different (Euclidean) distances between points in X. The aim is to retain as many of the points as possible such that certain imposed inter-pair distances are avoided. For example, we show that: (A) Given a set X of n points in the plane, an independent set of size $0.2293 n$ in the unit distance graph determined by X can be found in O(n^2) time. For any fixed k ∈ N there exists a constant c_k>0 such that for any set X of n points in the plane, and set D of size k, there exists a subset X' ⊆ X of size |X'| ≥ c_k |X| in which no pair of points is at some distance in D (we say that X' avoids distances in D). Such a set can be found efficiently. (B) (i) There is a subset of X of size n/2 that avoids the maximum distance; this bound cannot be improved. (ii) There is a subset of X of size 8n/47 that avoids both the minimum and maximum distance; on the other hand, there exists X such that at most 5n/16 points can be retained with this property. (iii) There is a subset of X of size n/7 whose diameter is at most half the original diameter; on the other hand, there exists X such that at most n/6 points can be retained with this property. (C) (i) For any ε>0, a (1−ε)-approximation for \textsc{MIS} in the minimum distance graph of n points in the plane can be found in 2^O(1/ε) n^O(1) time. (ii) Given a set X of n points in the plane, a maximum independent set in the graph of diameters can be computed in O(n^2) time. The techniques used to handle the planar case can be extended to R^d for any fixed dimension d.
ER -