More Like this

1. Segment Proximity Graphs and Nearest Neighbor Queries Amid Disjoint Segments

   https://doi.org/10.4230/LIPICS.ESA.2024.7  

   Agarwal, Pankaj K; Kaplan, Haim; Katz, Matthew J; Sharir, Micha (January 2024, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Chan, Timothy; Fischer, Johannes; Iacono, John; Herman, Grzegorz (Ed.)

   In this paper we study a few proximity problems related to a set of pairwise-disjoint segments in {ℝ}². Let S be a set of n pairwise-disjoint segments in {ℝ}², and let r > 0 be a parameter. We define the segment proximity graph of S to be G_r(S) := (S,E), where E = {(e₁,e₂) ∣ dist(e₁,e₂) ≤ r} and dist (e₁,e₂) = min_{(p,q) ∈ e₁× e₂} ‖p-q‖ is the Euclidean distance between e₁ and e₂. We define the weight of an edge (e₁,e₂) ∈ E to be dist(e₁,e₂). We first present a simple grid-based O(nlog² n)-time algorithm for computing a BFS tree of G_r(S). We apply it to obtain an O^*(n^{6/5}) + O(nlog²nlogΔ)-time algorithm for the so-called reverse shortest path problem, in which we want to find the smallest value r^* for which G_{r^*}(S) contains a path of some specified length between two designated start and target segments (where the O^*(⋅) notation hides polylogarithmic factors). Here Δ = max_{e ≠ e' ∈ S} dist(e,e')/min_{e ≠ e' ∈ S} dist(e,e') is the spread of S. Next, we present a dynamic data structure that can maintain a set S of pairwise-disjoint segments in the plane under insertions/deletions, so that, for a query segment e from an unknown set Q of pairwise-disjoint segments, such that e does not intersect any segment in (the current version of) S, the segment of S closest to e can be computed in O(log⁵ n) amortized time. The amortized update time is also O(log⁵ n). We note that if the segments in S∪Q are allowed to intersect then the known lower bounds on halfplane range searching suggest that a sequence of n updates and queries may take at least close to Ω(n^{4/3}) time. One thus has to strongly rely on the non-intersecting property of S and Q to perform updates and queries in O(polylog(n)) (amortized) time each. Using these results on nearest-neighbor (NN) searching for disjoint segments, we show that a DFS tree (or forest) of G_r(S) can be computed in O^*(n) time. We also obtain an O^*(n)-time algorithm for constructing a minimum spanning tree of G_r(S). Finally, we present an O^*(n^{4/3})-time algorithm for computing a single-source shortest-path tree in G_r(S). This is the only result that does not exploit the disjointness of the input segments. 

   more » « less
2. Clustering with Neighborhoods is Hard for Squares

   Klimenko, Georgiy; Raichel, Benjamin (July 2023, Proceedings of the 35th Canadian Conference on Computational Geometry)

   Pankratov, Denis (Ed.)

   In the clustering with neighborhoods problem one is given a set S of disjoint convex objects in the plane and an integer parameter k ≥ 0, and the goal is to select a set C of k center points in the plane so as to minimize the maximum distance of an object in S to its nearest center in C. Previously [HKR21] showed that this problem cannot be approximated within any factor when S is a set of disjoint line segments, however, when S is a set of disjoint disks there is a roughly 8.46 approximation algorithm and a roughly 6.99 approximation lower bound. In this paper we investigate this significant discrepancy in hardness between these shapes. Specifically, we show that when S is a set of axis aligned squares of the same size, the problem again is hard to approximate within any factor. This surprising fact shows that the discrepancy is not due to the fatness of the object class, as one might otherwise naturally suspect. 

   more » « less
3. On the rank of a random binary matrix

   https://doi.org/10.1137/1.9781611975482.58  

   Cooper, Colin; Frieze, Alan; Pegden, Wesley (January 2019, Proceedings of the annual ACM-SIAM Symposium on Discrete Algorithms)

   We study the rank of a random n × m matrix An, m; k with entries from GF(2), and exactly k unit entries in each column, the other entries being zero. The columns are chosen independently and uniformly at random from the set of all (nk) such columns. We obtain an asymptotically correct estimate for the rank as a function of the number of columns m in terms of c, n, k, and where m = cn/k. The matrix An, m; k forms the vertex-edge incidence matrix of a k-uniform random hypergraph H. The rank of An, m; k can be expressed as follows. Let |C2| be the number of vertices of the 2-core of H, and | E (C2)| the number of edges. Let m* be the value of m for which |C2| = |E(C2)|. Then w.h.p. for m < m* the rank of An, m; k is asymptotic to m, and for m ≥ m* the rank is asymptotic to m – |E(C2)| + |C2|. In addition, assign i.i.d. U[0, 1] weights Xi, i ∊ 1, 2, … m to the columns, and define the weight of a set of columns S as X(S) = ∑j∊S Xj. Define a basis as a set of n – 1 (k even) linearly independent columns. We obtain an asymptotically correct estimate for the minimum weight basis. This generalises the well-known result of Frieze [On the value of a random minimum spanning tree problem, Discrete Applied Mathematics, (1985)] that, for k = 2, the expected length of a minimum weight spanning tree tends to ζ(3) ∼ 1.202. 

   more » « less
4. Constraining the clustering transition for colorings of sparse random graphs

   Anastos, M.; Frieze, A.; Pegden, W. (January 2018, The electronic journal of combinatorics)

   Let $$\Omega_q$$ denote the set of proper $[q]$-colorings of the random graph $$G_{n,m}, m=dn/2$$ and let $$H_q$$ be the graph with vertex set $$\Omega_q$$ and an edge $$\set{\s,\t}$$ where $$\s,\t$$ are mappings $$[n]\to[q]$$ iff $$h(\s,\t)=1$$. Here $$h(\s,\t)$$ is the Hamming distance $$|\set{v\in [n]:\s(v)\neq\t(v)}|$$. We show that w.h.p. $$H_q$$ contains a single giant component containing almost all colorings in $$\Omega_q$$ if $$d$$ is sufficiently large and $$q\geq \frac{cd}{\log d}$$ for a constant $c>3/2$. 

   more » « less
5. Forbidding $$K_{2,t}$$ Traces in Triple Systems

   https://doi.org/10.37236/9760  

   Luo, Ruth; Spiro, Sam (April 2021, The Electronic Journal of Combinatorics)

   Let $$H$$ and $$F$$ be hypergraphs. We say $$H$$ {\em contains $$F$$ as a trace} if there exists some set $$S \subseteq V(H)$$ such that $$H|_S:=\{E\cap S: E \in E(H)\}$$ contains a subhypergraph isomorphic to $$F$$. In this paper we give an upper bound on the number of edges in a $$3$$-uniform hypergraph that does not contain $$K_{2,t}$$ as a trace when $$t$$ is large. In particular, we show that $$\lim_{t\to \infty}\lim_{n\to \infty} \frac{\mathrm{ex}(n, \mathrm{Tr}_3(K_{2,t}))}{t^{3/2}n^{3/2}} = \frac{1}{6}.$$ Moreover, we show $$\frac{1}{2} n^{3/2} + o(n^{3/2}) \leqslant \mathrm{ex}(n, \mathrm{Tr}_3(C_4)) \leqslant \frac{5}{6} n^{3/2} + o(n^{3/2})$$. 

   more » « less