More Like this

1. Eight-Partitioning Points in 3D, and Efficiently Too

   https://doi.org/10.4230/LIPIcs.SoCG.2024.8  

   Aronov, Boris; Basit, Abdul; Ramesh, Indu; Tasinato, Gianluca; Wagner, Uli (June 2024, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Mulzer, Wolfgang; Phillips, Jeff M (Ed.)

   An eight-partition of a finite set of points (respectively, of a continuous mass distribution) in ℝ³ consists of three planes that divide the space into 8 octants, such that each open octant contains at most 1/8 of the points (respectively, of the mass). In 1966, Hadwiger showed that any mass distribution in ℝ³ admits an eight-partition; moreover, one can prescribe the normal direction of one of the three planes. The analogous result for finite point sets follows by a standard limit argument. We prove the following variant of this result: Any mass distribution (or point set) in ℝ³ admits an eight-partition for which the intersection of two of the planes is a line with a prescribed direction. Moreover, we present an efficient algorithm for calculating an eight-partition of a set of n points in ℝ³ (with prescribed normal direction of one of the planes) in time O^*(n^{5/2}). 

   more » « less
2. On homogeneous Newton-Sobolev spaces of functions in metric measure spaces of uniformly locally controlled geometry

   https://doi.org/10.1007/s00229-025-01656-5  

   Gibara, Ryan; Kangasniemi, Ilmari; Shanmugalingam, Nageswari (July 2025, Manuscripta mathematica)

   We study the large-scale behavior of Newton-Sobolev functions on complete, connected, proper, separable metric measure spaces equipped with a Borel measure μ with μ(X) = ∞ and 0 < μ(B(x, r)) < ∞ for all x ∈ X and r ∈ (0, ∞). Our objective is to understand the relationship between the Dirichlet space D^(1,p)(X), defined using upper gradients, and the Newton-Sobolev space N^(1,p)(X)+ℝ, for 1 ≤ p < ∞. We show that when X is of uniformly locally p-controlled geometry, these two spaces do not coincide under a wide variety of geometric and potential theoretic conditions. We also show that when the metric measure space is the standard hyperbolic space ℍⁿ with n ≥ 2, these two spaces coincide precisely when 1 ≤ p ≤ n-1. We also provide additional characterizations of when a function in D^(1,p)(X) is in N^(1,p)(X)+ℝ in the case that the two spaces do not coincide. 

   more » « less
3. Enclosing Points with Geometric Objects

   https://doi.org/10.4230/LIPIcs.SoCG.2024.35  

   Chan, Timothy M; He, Qizheng; Xue, Jie (June 2024, Proc. 40th Sympos. Computational Geometry (SoCG))

   Mulzer, Wolfgang; Phillips, Jeff M (Ed.)

   Let X be a set of points in ℝ² and 𝒪 be a set of geometric objects in ℝ², where |X| + |𝒪| = n. We study the problem of computing a minimum subset 𝒪^* ⊆ 𝒪 that encloses all points in X. Here a point x ∈ X is enclosed by 𝒪^* if it lies in a bounded connected component of ℝ²∖(⋃_{O ∈ 𝒪^*} O). We propose two algorithmic frameworks to design polynomial-time approximation algorithms for the problem. The first framework is based on sparsification and min-cut, which results in O(1)-approximation algorithms for unit disks, unit squares, etc. The second framework is based on LP rounding, which results in an O(α(n)log n)-approximation algorithm for segments, where α(n) is the inverse Ackermann function, and an O(log n)-approximation algorithm for disks. 

   more » « less
4. Sparse Bounded Hop-Spanners for Geometric Intersection Graphs

   https://doi.org/10.4230/LIPIcs.SoCG.2025.17  

   Bhore, Sujoy; Chan, Timothy M; Huang, Zhengcheng; Smorodinsky, Shakhar; Tóth, Csaba D (January 2025, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Aichholzer, Oswin; Wang, Haitao (Ed.)

   We present new results on 2- and 3-hop spanners for geometric intersection graphs. These include improved upper and lower bounds for 2- and 3-hop spanners for many geometric intersection graphs in ℝ^d. For example, we show that the intersection graph of n balls in ℝ^d admits a 2-hop spanner of size O^*(n^{3/2 - 1/(2(2⌊d/2⌋ + 1))}) and the intersection graph of n fat axis-parallel boxes in ℝ^d admits a 2-hop spanner of size O(n log^{d+1}n). Furthermore, we show that the intersection graph of general semi-algebraic objects in ℝ^d admits a 3-hop spanner of size O^*(n^{3/2 - 1/(2(2D-1))}), where D is a parameter associated with the description complexity of the objects. For such families (or more specifically, for tetrahedra in ℝ³), we provide a lower bound of Ω(n^{4/3}). For 3-hop and axis-parallel boxes in ℝ^d, we provide the upper bound O(n log ^{d-1}n) and lower bound Ω(n ({log n}/{log log n})^{d-2}). 

   more » « less
5. A Holocene record of Pacific Decadal Oscillation (PDO)-related hydrologic variability in Southern California (Lake Elsinore, CA)

   https://doi.org/10.1007/s10933-010-9454-0  

   Kirby, M. E.; Lund, S. P.; Patterson, W. P.; Anderson, M. A.; Bird, B. W.; Ivanovici, L.; Monarrez, P.; Nielsen, S. (October 2010, Journal of Paleolimnology)

   High-resolution terrestrial records of Holocene climate from Southern California are scarce. Moreover, there are no records of Pacific Decadal Oscillation (PDO) variability, a major driver of decadal to multi-decadal climate variability for the region, older than 1,000 years. Recent research on Lake Elsinore, however, has shown that the lake’s sediments hold excellent potential for paleoenvironmental analysis and reconstruction. New 1-cm contiguous grain size data reveal a more complex Holocene climate history for Southern California than previously recognized at the site. A modern comparison between the twentieth century PDO index, lake level change, San Jacinto River discharge, and percent sand suggests that sand content is a reasonable, qualitative proxy for PDO-related, hydrologic variability at both multi-decadal-to-centennial as well as event (i.e. storm) timescales. A depositional model is proposed to explain the sand-hydrologic proxy. The sand-hydrologic proxy data reveal nine centennial-scale intervals of wet and dry climate throughout the Holocene. Percent total sand values >1.5 standard deviation above the 150–9,700 cal year BP average are frequent between 9,700 and 3,200 cal year BP (n = 41), but they are rare from 3,200 to 150 cal year BP (n = 6). This disparity is interpreted as a change in the frequency of exceptionally wet (high discharge) years and/or changes in large storm activity. A comparison to other regional hydrologic proxies (10 sites) shows more then occasional similarities across the region (i.e. 6 of 9 Elsinore wet intervals are present at >50% of the comparison sites). Only the early Holocene and the Little Ice Age intervals, however, are interpreted consistently across the region as uniformly wet (≥80% of the comparison sites). A comparison to two ENSO reconstructions indicates little, if any, correlation to the Elsinore data, suggesting that ENSO variability is not the predominant forcing of Holocene climate in Southern California. 

   more » « less