More Like this

1. Tight Bounds on the Number of Closest Pairs in Vertical Slabs

   https://doi.org/10.4230/LIPIcs.WADS.2025.8  

   Biniaz, Ahmad; Bose, Prosenjit; Chung, Chaeyoon; De_Carufel, Jean-Lou; Iacono, John; Maheshwari, Anil; Odak, Saeed; Smid, Michiel; Tóth, Csaba D (January 2025, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Morin, Pat; Oh, Eunjin (Ed.)

   Let S be a set of n points in ℝ^d, where d ≥ 2 is a constant, and let H₁,H₂,…,H_{m+1} be a sequence of vertical hyperplanes that are sorted by their first coordinates, such that exactly n/m points of S are between any two successive hyperplanes. Let |A(S,m)| be the number of different closest pairs in the {(m+1) choose 2} vertical slabs that are bounded by H_i and H_j, over all 1 ≤ i < j ≤ m+1. We prove tight bounds for the largest possible value of |A(S,m)|, over all point sets of size n, and for all values of 1 ≤ m ≤ n. As a result of these bounds, we obtain, for any constant ε > 0, a data structure of size O(n), such that for any vertical query slab Q, the closest pair in the set Q ∩ S can be reported in O(n^{1/2+ε}) time. Prior to this work, no linear space data structure with sublinear query time was known. 

   more » « less
2. On Locality-Sensitive Orderings and Their Applications

   https://doi.org/10.4230/LIPIcs.ITCS.2019.21  

   Chan, Timothy M.; Har-Peled, Sariel; Jones, Mitchell (January 2019, Proc. Innovations in Theoretical Computer Science Conference (ITCS))

   For any constant d and parameter epsilon > 0, we show the existence of (roughly) 1/epsilon^d orderings on the unit cube [0,1)^d, such that any two points p, q in [0,1)^d that are close together under the Euclidean metric are "close together" in one of these linear orderings in the following sense: the only points that could lie between p and q in the ordering are points with Euclidean distance at most epsilon | p - q | from p or q. These orderings are extensions of the Z-order, and they can be efficiently computed. Functionally, the orderings can be thought of as a replacement to quadtrees and related structures (like well-separated pair decompositions). We use such orderings to obtain surprisingly simple algorithms for a number of basic problems in low-dimensional computational geometry, including (i) dynamic approximate bichromatic closest pair, (ii) dynamic spanners, (iii) dynamic approximate minimum spanning trees, (iv) static and dynamic fault-tolerant spanners, and (v) approximate nearest neighbor search. 

   more » « less
3. Marcinkiewicz Averages of Smooth Orthogonal Projections on Sphere

   https://doi.org/10.1007/s00041-022-09966-y  

   Bownik, Marcin; Dziedziul, Karol; Kamont, Anna (October 2022, Journal of Fourier Analysis and Applications)

   Abstract We construct a single smooth orthogonal projection with desired localization whose average under a group action yields the decomposition of the identity operator. For any full rank lattice $$\Gamma \subset \mathbb {R}^d$$ Γ ⊂ R d , a smooth projection is localized in a neighborhood of an arbitrary precompact fundamental domain $$\mathbb {R}^d/\Gamma $$ R d / Γ . We also show the existence of a highly localized smooth orthogonal projection, whose Marcinkiewicz average under the action of SO ( d ), is a multiple of the identity on $$L^2(\mathbb {S}^{d-1})$$ L 2 ( S d - 1 ) . As an application we construct highly localized continuous Parseval frames on the sphere. 

   more » « less
4. 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
5. Test of lepton flavor universality and search for lepton flavor violation in B → Kℓℓ decays

   https://doi.org/10.1007/JHEP03(2021)105  

   Choudhury, S.; Sandilya, S.; Trabelsi, K.; Giri, A.; Aihara, H.; Al Said, S.; Asner, D. M.; Atmacan, H.; Aulchenko, V.; Aushev, T.; et al (March 2021, Journal of High Energy Physics)

   null (Ed.)

   A bstract We present measurements of the branching fractions for the decays B → Kμ + μ − and B → Ke + e − , and their ratio ( R K ), using a data sample of 711 fb − 1 that contains 772 × 10 6 $$ B\overline{B} $$ B B ¯ events. The data were collected at the ϒ(4 S ) resonance with the Belle detector at the KEKB asymmetric-energy e + e − collider. The ratio R K is measured in five bins of dilepton invariant-mass-squared ( q 2 ): q 2 ∈ (0 . 1 , 4 . 0) , (4 . 00 , 8 . 12) , (1 . 0 , 6 . 0), (10 . 2 , 12 . 8) and ( > 14 . 18) GeV 2 /c 4 , along with the whole q 2 region. The R K value for q 2 ∈ (1 . 0 , 6 . 0) GeV 2 /c 4 is $$ {1.03}_{-0.24}^{+0.28} $$ 1.03 − 0.24 + 0.28 ± 0 . 01. The first and second uncertainties listed are statistical and systematic, respectively. All results for R K are consistent with Standard Model predictions. We also measure CP -averaged isospin asymmetries in the same q 2 bins. The results are consistent with a null asymmetry, with the largest difference of 2.6 standard deviations occurring for the q 2 ∈ (1 . 0 , 6 . 0) GeV 2 /c 4 bin in the mode with muon final states. The measured differential branching fractions, $$ d\mathrm{\mathcal{B}} $$ d ℬ /dq 2 , are consistent with theoretical predictions for charged B decays, while the corresponding values are below the expectations for neutral B decays. We have also searched for lepton-flavor-violating B → Kμ ± e ∓ decays and set 90% confidence-level upper limits on the branching fraction in the range of 10 − 8 for B + → K + μ ± e ∓ , and B 0 → K 0 μ ± e ∓ modes. 

   more » « less