Papers

Curves as input data naturally arise in a variety of fields including finance, seismology, medicine, spatio-temporal data mining, malicious activity detection, and more. A common way to analyze these data sets is to do similarity matching or clustering. The most common metrics used for measuring similarity of curves are Dynamic Time Warping (DTW) and Fréchet distance. These metrics are sensitive to sampling rate and outliers respectively, and do not yield robust outcomes. Continuous Dynamic Time Warping (CDTW) is a more robust distance metric that improves upon DTW and Fréchet distances. Existing algorithms for CDTW are either exact algorithms that focus on non-Euclidean norms and piecewise linear curves, or approximation algorithms limited to piecewise linear curves. We present an approximation algorithm for computing the CDTW distance under Euclidean norm between piecewise (higher degree) algebraic curves. That is, we present a fully polynomial-time approximation scheme (FPTAS) of multiplicative error $\varepsilon$, with $O \left( (m+n)^{\frac{19}{6}} (\frac{1}{\varepsilon})^{\frac{10}{3}} \log \left( \frac{ (m+n) }{\varepsilon^2} \right) \right)$ complexity, where $m$ and $n$ are the number of pieces of the two input curves.

Existing 3D mesh reconstruction methods from Gaussian scene representations predominantly rely on iterative optimization, resulting in slow inference and limited scalability to high-resolution inputs. In this paper, we present AnyGS2Mesh, the first feed-forward framework for directly reconstructing 3D meshes from 3D Gaussian Splatting representations with support for arbitrary input image resolutions. Our approach incorporates a Gaussian-Guided Transformer architecture that exploits explicit 3D geometric priors for efficient mesh generation. We introduce three key components: (1) a Gaussian-Guided Spatial Reasoning Transformer represents Gaussian primitives as structured 3D tokens and jointly reasons over Gaussian and image features; (2) a Streaming and Patchwise Geometry Encoder processes native-resolution views sequentially and aggregates information across variable-length view sets; (3) a Scale-Aligned Hybrid Depth Refiner uses a PatchFusion-style encoder–decoder to fuse RGB-conditioned predicted depth with Gaussian-rendered metric depth, combining fine local structures with globally consistent metric scale. The refined depth maps are integrated through TSDF fusion, followed by Marching Cubes for deterministic mesh extraction. Extensive experiments show that AnyGS2Mesh achieves state-of-the-art reconstruction quality while significantly reducing inference time compared with optimization-based baselines, enabling near-real-time, high-quality mesh reconstruction. Our results demonstrate the potential of combining Gaussian representations and feed-forward Transformer architectures for scalable 3D geometry reconstruction. The code will be made publicly available upon acceptance.

Let $0 < \alpha \leq 1/2$. We say that a finite point set $P$ in $\mathbb{R}^d$ is $\alpha$-split by a hyperplane $h$ if each of the closed half-spaces determined by $h$, contains at least $\alpha |P|$ of the points of $P$. We further say $P$ is $\alpha$-split by a $k$-dimensional flat $\tau$ if $P$ is $\alpha$-split by any hyperplane through $\tau$. In the standard notation (which coincides with Tukey depth for $k= 0$), the $k$-flat $\tau$ has depth $\alpha$ with respect to $P$. We establish interesting Helly-type theorems for splitting families of finite point sets in $\mathbb{R}^d$. Unlike the classical sufficient Helly-type criteria for transversals to families of compact convex sets, which exist only for point and hyperplanes, our results extend to splitting families of point sets by collections of $k$-flats of arbitrary dimensionality $ 0 \leq k \leq d-1$.

Albertson's conjecture states that every graph of chromatic number r has crossing number at least that of the complete graph K_r. We prove the conjecture for all r. The proof combines new clique-sensitive edge bounds for critical graphs, maximum-clique sampling, and a reserved immersion construction. For graphs of order close to r, we construct edge-disjoint routes while preserving a complete bipartite subgraph whose forced crossings compensate for those introduced when the immersion is smoothed into a drawing. For larger orders, we derive explicit edge bounds using independent-triple deletion and structural properties of critical graphs, then combine them with sampling inequalities that account for crossings within a maximum clique. The remaining numerical inequalities are certified using exact rational arithmetic, with a reproducible certificate and standalone Python verifier.

This paper introduces the Sierpiński-Knopp (SK) Wasserstein distance, a fast metric between persistence diagrams. The SK-Wasserstein distance, denoted $d_{\mathrm{SK}}$, maps diagram points and their diagonal projections to the unit interval via the Sierpiński-Knopp space-filling curve on the upper diagonal triangle. The encoded point sets are then efficiently matched via one-dimensional optimal assignment, in \(O(N\log N)\) steps, yielding an explicit diagonal-aware point assignment between the two input persistence diagrams. We show that the SK-Wasserstein distance controls the classical \(2\)-Wasserstein distance between diagrams, admits an explicit isometric embedding into a Hilbert space, and induces a positive-definite Gaussian kernel, making the resulting geometry directly compatible with Euclidean and kernel-based learning methods. A tighter surrogate dissimilarity, noted \(W_\Gamma\), is also introduced based on the point assignments along the curve. Experiments on 12 scientific collections comprising 227 diagrams show median per-collection speedup of \(d_{\mathrm{SK}}\) over state-of-the-art approximations of \(W_2\) is \(626\times\), while the aggregate speedup over the full benchmark is \(2100\times\). Average-linkage partitions obtained from \(d_{\mathrm{SK}}\) and \(W_\Gamma\) each exactly match the corresponding \(W_2\) partition on 8 of the 12 collections. Hilbert \(k\)-means and Gaussian spectral clustering, both based on \(d_{\mathrm{SK}}\), achieve mean adjusted Rand indices (ARI) of \(0.756\) and \(0.800\), respectively, with respect to the benchmark reference partitions, compared to \(0.750\) obtained by average linkage on \(W_2\). The Gaussian \(d_{\mathrm{SK}}\) kernel supports other kernel-based analysis tasks, as illustrated by its use for contiguous segmentation of ordered diagram collections in our experiments.

This paper investigates $k$-visibility, where a line of sight can penetrate up to $k$ obstacles. While computing the $k$-visibility polygon from a single query point is well-studied, existing spatial preprocessing approaches rely on full $O(n^2)$ line arrangements through all vertex pairs without characterizing the minimal set of topological boundaries. We present a refined cell decomposition framework that isolates the exact geometric events governing $k$-visibility: primary vertex horizon lines and secondary mutually critical hinge lines. We prove that this minimal set of partition lines yields a spatial decomposition of $\Theta(n^4)$ cells within which the combinatorial structure of the $k$-visibility polygon remains strictly invariant. By leveraging a combinatorial $\delta$-compression scheme across cell boundaries, we achieve an overall storage complexity of $\mathcal{O}(n^4)$ while supporting optimal $\mathcal{O}(\log n + m)$ query time to reconstruct explicit $k$-visibility polygons of size $m$. Our framework naturally extends to polygons containing holes.

On the once-punctured torus, we give an exact formula for the number of curves in any given mapping class group orbit of given word length. This settles a conjecture of Chas in [Cha16].

Triangulate a simple quadrilateral by connecting all vertices to an additional point. If the vertices carry values, the piecewise linear function can be assigned a Dirichlet energy. We show that the minimal Dirichlet energy as a function of the location of the inserted point is convex, and the location of the minimum is independent of the values at the corners - a quadrilateral has a discrete harmonic center, characterized by an equilibrium of currents across the inserted edges. It turns out that the fixed points of the Möbius involution swapping opposite corners of the quadrilateral are critical points of this energy, so the discrete harmonic center is Möbius-covariant. For tangential and cyclic quadrilaterals the center admits simple closed forms related to the circle centers. The center and its data-independence generalize to polytopes with d + 2 vertices in dimension d, but the conformal characterizations are special to four points in the plane.

Let $P$ be a polygonal curve with $n$ vertices in the plane. We construct a data structure of size $O(n \log n)$ suited for simplification queries of the following kind. Given a query line $\ell$ and an integer $k\ge1$, find a curve $Q$ on $\ell$ with at most $k$ vertices that minimizes the discrete Fréchet distance to $P$, among all such curves. Using our data structure, a query can be handled in $O(k^2 \log^3 n + k\log^4 n)$ time. More generally, a geometric tree $T$ on $n$ vertices in the plane can be preprocessed into a near-linear-size structure so that, given a pair $u$, $v$ of its vertices, a line $\ell$, and an integer $k\ge1$, one can find a curve $Q$ on $\ell$ with at most $k$ vertices that minimizes the discrete Fréchet distance to the path from $u$ to $v$ in $T$, in time $O(k^2 \mathop{polylog} n)$. For the general dimension-reduction problem, where $P$ is a curve in $\mathbb{R}^d$ ($d \ge 3$), $0 < \varepsilon_0 < 1$ is a real parameter, and a query specifies a $g$-flat $h$ ($1 \le g \le d-1$) and an integer $k \ge 1$, we construct a data structure of size $O(n\log n + f(\varepsilon_0) n)$, where $f(\varepsilon_0)=(1+1/\varepsilon_0)^{(d-1)/2}$, that allows us to find a curve $Q$ on $h$ with at most $k$ vertices, whose discrete Fréchet distance to $P$ is at most $1+\varepsilon_0$ times the distance of $Q^*$ to $P$, where $Q^*$ is such a curve that minimizes the distance to $P$. The query handling time is $O(f(\varepsilon_0) k^2 \log^2 n)$.

A universal cover is a convex set in the plane that contains a congruent copy of every planar set of diameter one. Lebesgue asked in 1914 for one of least area, and the value is not known. We prove that every convex universal cover has area at least 0.8344, improving on 0.832, published in 2005, and 0.833, in a 2026 preprint, both of which come from a disc together with an equilateral triangle and a regular pentagon. Our test sets are instead curves of constant width: the disc, the Reuleaux triangle and the Reuleaux pentagon. Each contains the regular polygon it is built on, so the family is strictly larger at the same number of bodies and the same number of placement parameters, and we show that the classical configuration admits an arrangement whose hull has area below 0.8336, so no bound drawn from those three sets by this argument reaches ours. Curves of constant width were proposed for this role, and explored numerically, by Gibbs in 2014; what is added here is a proof. It consists of an analytic reduction followed by one finite computation. The reduction bounds the hull area from below over an entire box of placements at once, by eroding each Reuleaux polygon to a fixed set contained in every placement that box allows. The computation is an exhaustive subdivision of the resulting five-dimensional space, recorded as a certificate of 486,799,600 nodes and checked by a verifier independent of the search, with a rigorous bound on its floating point error some thousands of times smaller than the margin the verification attains.

Most shape reconstruction methods assume measurements defined over planar sensing domains, such as RGB images or depth maps. In this paper, we use a curved capacitive textile as a shape sensor, treating its surface as a non-planar sensing manifold. Each scan is represented as a capacitive proximity field on this manifold, induced by the interaction between the curved electrode layout and nearby object geometry. We introduce a multi-view feedforward reconstruction model that aggregates these fields across known sensor views and recovers the observed object shape. Simulated and physical experiments demonstrate robust reconstruction from capacitive proximity signals acquired on curved sensing surfaces, pointing toward a new route to robotic near-field geometric awareness via embodied sensing.

We find explicit ridge unfoldings of the three exceptional 4D polytopes (24-cell, 120-cell, 600-cell) that result in overlaps of their facets. These failures bring an end to the full classification of regular polytopes with the all-net property.

In recent years, kirigami metamaterials have been widely studied and applied in science and engineering. While various two- and three-dimensional kirigami design methods have been developed, most of them are only applicable to a limited class of kirigami structures. In this work, we develop a unified framework for kirigami design that encompasses a wide range of 2D-to-2D, 2D-to-3D, and 3D-to-3D shape-morphing effects, as well as additional geometric and physical properties such as compact reconfigurability and rigid deployability. In particular, by reformulating the design task as a length-based constrained optimization problem and solving it simultaneously for multiple target states of the kirigami structure, our unified design framework enables greater design flexibility and stronger theoretical support. Experimental results with a wide range of shape-morphing effects are presented to demonstrate the effectiveness of our framework. We further present a rigorous theoretical analysis of several key aspects of kirigami design, covering inertia transposition, aspect-ratio law, and angle defects, thereby elucidating important design rules and limitations. Altogether, our work paves a new way for the design of shape-morphing mechanical metamaterials.

Hierarchical splines are an important part of multiscale and adaptive isogeometric analysis formulations. The Bézier meshes of these splines are an essential part of their definition and of several important hierarchical spline algorithms, such as adaptive refinement and Bézier extraction. Topological data associated with the Bézier mesh-such as adjacency information-can be used to improve the performance of many of these algorithms as well as downstream applications of the splines, but typical hierarchical spline formulations do not compute the topological data, storing instead just a list of elements. In this work we present algorithms to build a performant topological data structure, namely the combinatorial map, to represent Bézier meshes of hierarchical splines over cubical cell complexes where the refinement levels have conforming Bézier meshes. This includes hierarchical and truncated hierarchical B-splines, as well as subsets of other hierarchical spline formulations. We show the performance characteristics of the construction algorithms of these hierarchical combinatorial maps, as well as an example use case, showing that the topological information can provide up to an order of magnitude reduction in computation time in downstream applications of the splines.

While neural rendering methods such as 3D Gaussian Splatting achieve remarkable visual fidelity, traditional polygonal meshes remain the backbone of established graphics pipelines. Triangle splatting bridges this gap by optimizing triangle primitives as differentiable splats, producing representations that are closer to mesh-based workflows. Central to these methods is the kernel function that softens triangle boundaries to propagate gradients to vertex positions. Existing triangle splatting methods make inconsistent choices of kernel functions, and analysis of these kernels' optimization behavior has been limited to unstructured triangle soups for novel-view synthesis. In this work, we consider triangle splatting as a generic tool for photometric optimization, comparing kernel properties through two complementary tasks: mesh optimization for shape reconstruction and triangle soup optimization for novel-view synthesis. Along with the analysis, we introduce an elastic kernel function that features bilateral gradient support across the boundary and an adaptive boundary value, which are shown to be essential for robust optimization. Under isolated comparison, our elastic kernel outperforms existing kernels on shape reconstruction and in the majority of novel-view synthesis benchmarks, demonstrating the importance of kernel design in the effectiveness and versatility of triangle splatting.

We study online search for an unknown affine hyperplane in $\mathbb{R}^D$, for arbitrary fixed finite dimension. Building on a companion self-similar cell reduction and support-function formulation, we ask how the mechanism changes as the normal space grows from $\mathbb{S}^0$ to $\mathbb{S}^{D-1}$. In $D=1$, alternation and productivity yield an equal-ripple principle and the exact stationary constant $9$. In $D=2$, the analogous relative equilibrium is a logarithmic spiral whose bottleneck chord imposes tangency and selects the pitch. For exponential orbits $\Gamma(\sigma)=e^{\kappa\sigma}\omega(\sigma)$, we develop log-directional geometry, exponentially discounted memory, gauges, and recursive hyperspherical parametrizations. Without a shape ansatz, the bottleneck admits a certificate supported by at most $D$ historical suppliers, and at globally worst phases the current point lies on the active face. Within regular chambers we derive exact variation, tangency, pitch, age, and, in $D=3$, delay-system identities. Odd-dimensional obstructions, antipodal subclasses, and harmonic towers provide constraints and explicit candidate families but are not claimed globally optimal. Finally, the N-COMP theorem shows that $C_D^*$ is a computable real for every fixed finite $D$ and that algebraic polygonal $\varepsilon$-optimal cells can in principle be synthesized. Numerical screening through $D=10$ is kept separate from the proved results.

A shoreline-search path starts at the origin and must meet an unknown affine line, without knowing either its normal or its distance. We first establish a self-similar reduction theorem for homogeneous search problems whose historical information is a record profile updated by pointwise maximum. Two quasi-returns of the normalized state delimit a block that renews the required profile by itself; a short connector closes this block into a cell. Every finite-ratio path can therefore be approximated, with arbitrarily small loss, by repetitions of a single cell at all scales. The main chain is then made effective. A finite coding of the state space computably bounds the scale factor and normalized length of a nearly optimal cell. For planar Shoreline search, the support function of the convex hull gives an exact cell functional. A one-sided polygonalization then reduces the problem to a computable number of vertices, after which quantifier elimination decides whether a polygonal cell exists below a rational threshold. It follows that the optimal deterministic planar Shoreline value $C_2^*$ is a computable real: for every rational $\epsilon>0$, an algorithm terminates with a rational interval of width at most $\epsilon$ containing $C_2^*$. Additional results—sliding memory, Bellman transitions, deadlines, geometric filters, and relative equilibria—are presented separately as a toolbox for certified computation and for the study of spiral rigidity; they are not used in the computability proof.

We study $\ell_0$ isoperimetry for a convex body $K\subset \mathbb{R}^n$, $n\ge2$. For a Borel set $S\subset K$, let $\partial_0^K S$ be the set of points in $K \setminus S$ that can be reached from $S$ by changing at most one coordinate (i.e. the $\ell_0$ boundary of $S$). Suppose that, for some unconditional convex body $Q \subset \mathbb{R}^n$, numbers $r,R>0$, and possibly different centers $x_0,y_0$, \[ x_0+rQ \subset K\subset y_0+RQ. \] Writing $s=\text{vol}(S)/\text{vol}(K)$, we prove that whenever $0<s \le 1/2$, \[ \frac{\text{vol}(\partial_0^K S)}{\text{vol}(S)} \ge \frac{cr}{nR} \min\left\{1,\frac{\log(e/s)}{n}\right\}, \] where $c > 0$ is an absolute constant. Consequently, the associated $\ell_0$-isoperimetric coefficient is at least $cr/(n^2R)$. Previous direct lower bounds were only known for $\ell_2$ and $\ell_\infty$ regularity whereas our lower bound holds directly for any $Q$-regularity, where $Q$ is an unconditional convex body. Compared to $\ell_2$ and $\ell_\infty$ regularity, our lower bound result improves upon the previously best known lower bounds, for any $s$, by a factor of $n$. As an application of our result, we give improved mixing time bounds for the Coordinate Hit and Run walk (CHAR). Our proof of the lower bound is based on a modification of the method of canonical paths applied to a continuous Hamming graph over our convex body. Our construction of canonical paths can be viewed as a suitable coordinate discretization of certain mass transport maps from $S$ to $S^c$. We also give complementary upper-bounds for any $Q$-regularity, with an overall factor of $n$ gap between the two.

We study the edge-power cost of the labelled tree generated by the $\gamma$-strategy, a constant-gain rule for sequential Euclidean connections. Starting with $x_0=p_0$, each input point $p_i$ is attached to $x_{i-1}$, and the state is updated by $x_i=\gamma x_{i-1}+(1-\gamma)p_i$. Retaining $x_i$ subdivides the insertion segment into a spine edge and a leaf edge. The memory parameter $\gamma$ controls how long earlier points influence subsequent attachment points. We minimize the sum of the $\alpha$-powers of the edge lengths under independent uniform input and arbitrary input sequences. For uniform points in the unit ball, the stationary problem has a transition at $\alpha=1$. Its continuous extension is minimized at the boundary for $0<\alpha\leq1$, while every global minimizer is interior for $\alpha>1$. We determine the finite optimizer in the joint window $\alpha_N=1+\varepsilon_N$, $\varepsilon_N\log N\to\lambda$. Below an explicit threshold it lies on the $N^{-1/2}$ scale, at the threshold its scale is $\sqrt{\log N/(N\log\log N)}$, and above the threshold it approaches an explicit stationary root with two computable corrections. A second threshold identifies the governing correction, and differentiated estimates prove eventual uniqueness. At $\alpha=3d+8$, the linear coefficient at the stationary endpoint changes sign and a branch of strict local maxima enters the parameter interval. For arbitrary input sequences, the optimal parameter and asymptotic worst-case edge-power cost per point are explicit for $0<\alpha\leq3$. At high powers, periodic antipodal block inputs give explicit lower bounds which, with a separation argument, show that the optimized cost is asymptotic to $2\log2/\log\alpha$. Exact results for powers two and four, a rational recursion for every even power, and a high-dimensional expansion complete the analysis.

In ranked-choice voting, a Condorcet-winning set is a group of candidates for which no outside candidate is preferred to every member of the group by a majority of voters. We study Condorcet-winning sets in planar metric elections, where voters rank candidates according to their distance under a given norm. We formulate general metric elections, peer selection, and the one-round Voronoi game as instances of a two-player Stackelberg game and place these problems in a common hierarchy. We also introduce a new variant, which we call strong peer selection. Our main result concerns peer selection under the $\ell_1$ and $\ell_\infty$ norms. We prove that every planar instance admits a Condorcet-winning set of size at most three, even under strong peer selection. This follows from a new result for strong rectangular $\varepsilon$-nets. We show that, for every set of points in the plane, one can choose at most three input points that intersect every axis-parallel rectangle containing more than half of the points, improving the previous threshold of $9 / 16$ due to Ashok et al. Under the $\ell_2$ norm, we prove that every planar metric election admits a Condorcet-winning set of size at most four, improving on the general bound of five due to Song et al. Finally, we give new norm-independent bounds for the one-round Voronoi game.

We present results on the approximate computation of stable invariants for filtrations of finite metric spaces in the context of persistent homology. We establish novel approximation algorithms in the setting of $n$-point metric spaces where the growth of the doubling dimension is in $o(\log n)$ and the diameter is bounded. In the $1$-parameter case, by revisiting known techniques (greedy permutations) in a new way, we derive the first linear-time algorithms for the problem of computing additive $\varepsilon$-approximations of any stable barcode. By deriving bounds on the convergence rate and the approximation quality of uniform samples, we extend the approach to selected multiparameter filtrations. We show that for normalized measure bifiltrations, including the multicover and subdivision-Rips bifiltration, any stable invariant can be probabilistically approximated in time constant in $n$. The constants in the running times of our algorithms depend on the doubling dimension, the diameter and the success probability. We further study the problem through the lens of fine-grained complexity and show that computing the rank of a matrix reduces to that of approximating the barcode of the Vietoris–Rips or Čech filtration. We present two variants of the reduction, one for sufficiently good additive approximations and the other for any constant factor multiplicative approximations.

Motivated by the recent introduction of chromatic persistent homology, we generalize the Euclidean minimum spanning tree (EMST) for $n$ points in $\mathbb{R}^2$ to the lunar EMST for the case in which the points come in $s+1$ colors. Calling the intersection of $s+1$ disks of radius $r$ centered at points with pairwise different colors a lune, the generalized EMST reflects the history of the union of lunes as $r$ goes from $0$ to $\infty$, and its cost is twice the difference between the radii when the arcs and nodes of the tree are formed. If the points are chosen uniformly at random in $[0,1]^2$ and colored randomly, the expected cost converges to some constant (that depends on $s$) times $\sqrt{n}$, as $n$ goes to infinity. The main contribution of this paper is a proof that this constant exists, however similar to the case of the classic EMST, its precise value remains elusive.

We study nearest and farthest Voronoi diagrams of lines in $\mathbb{R}^3$ under the Euclidean metric when all $n$ lines belong to one ruling of a smooth doubly ruled real quadric. For arbitrary line sites, the combinatorial complexity of the nearest Voronoi diagram is known only to lie between $\Omega(n^2)$ and $O(n^{3+\varepsilon})$. Under general-position assumptions, we prove that both diagrams in the ruling class have at most $4n(n-3)$ vertices and $O(n^2)$ total combinatorial complexity. Conversely, for every $n \ge 4$, one ruling of a fixed non-rotational one-sheeted hyperboloid contains a general-position set of $n$ lines with at least $(n-2)(n-3)/2$ distinct regular nearest vertices, where regular means that exactly four lines support the vertex and their three defining bisectors meet transversely. Thus the worst-case complexity of the nearest Voronoi diagram in this class is $\Theta(n^2)$, while the farthest diagram has $\Theta(n^2)$ complexity for every general-position input, since it has exactly $n(n-1)$ three-dimensional cells. Under the Plücker embedding, the ruling is a conic, and the condition for a line to be tangent to a Euclidean sphere restricts to a binary quartic. At a regular vertex, the four supporting parameters exhaust its roots, and sign alternation forces two arcs of the parameter circle to be site-free. This leaves only $n(n-3)/2$ possible cyclic support types, while Bézout's theorem bounds the number of centers for each type by eight. The same reduction yields an exact $O(n^2)$-time algorithm that, after cyclically sorting the site parameters, enumerates all finite nearest and farthest vertices as constant-degree real univariate representations.

Operational requirements developed with the City of Braunschweig frame municipal micromobility planning under geofenced exclusions, mandatory retained sites, spacing rules, and area-level caps. Each policy edit requires a new feasible plan; full-set greedy takes tens of seconds per alternative at city scale. We present CLIPPER (Constraint-exact Low-latency Iterative Planning with Pooled Evaluation and Replay). It forms bounded candidate pools but recomputes exact current gains and checks every active constraint before selection. Coverage from each candidate alone sets the initial order. Offline full-set scans measure gains omitted by the pool; online, a conservative bound triggers expansion or audit. CLIPPER-F gives each proposal group the same number of candidate slots. Across Braunschweig, Munich, and Berlin, its mean coverage over complete chains stays within 0.245 percentage points of full-set greedy under the same policy, with 13.6–28.9 times lower mean rollout time. CLIPPER-A instead distributes one shared candidate budget across the groups. Under its coverage-prioritized policy, it uses 9–15% of full-set greedy's rollout time under the same policy, with mean gaps of 1.82 percentage points in Braunschweig, 0.12 in Munich, and 0.27 in Berlin. Together, CLIPPER enables rapid, replayable comparison of recorded city-scale planning states while enforcing every encoded model constraint.

Points in the unit ball of $\mathbb R^d$ are processed sequentially. Each new point $p_i$ is connected to a state $x_{i-1}$ that summarizes earlier observations, after which $x_i=\gamma x_{i-1}+(1-\gamma)p_i$, with $0\leq\gamma\leq1$. The cost is the sum of the $\alpha$-powers of the connection lengths. This constant-gain rule interpolates between the input-order path and the star centered at the initial point. For independent uniform points, we establish the stationary insertion-length distribution and prove that it decreases in stochastic order as $\gamma$ increases. If $d+\alpha>2$, or if $(d,\alpha)=(1,1)$, the optimal constant parameter satisfies $1-\gamma_N^*=\Theta(N^{-1/2})$, with an explicit asymptotic constant and closed bounds. For $\alpha=1$, its leading expected tree length equals that of the center star and is eventually smaller than the expected lengths of both endpoint constructions. For $\alpha=2$, the optimizer is unique and characterized exactly. For the same $N$, choosing $1-\gamma_N$ as a fixed positive multiple of $N^{-1/2}$ gives a sharp two-term expansion of the expected uniform-input cost and a maximal adversarial mean cost of $1+O(N^{-1/2})$. For every fixed $0\leq\gamma<1$ and $0<\alpha\leq3$, the exact asymptotic adversarial value is $(2/(1+\gamma))^\alpha$. When $d\geq2$, exponential weighting is within a factor smaller than $1.161^\alpha$ of the best fixed nonnegative weighted rule with the same average look-back, for $0<\alpha\leq3$. Comparison with the running mean highlights its time-homogeneous update, stationary coefficient profile, and fixed effective memory.

Hyperbolic surfaces are a fundamental object in mathematics and play an increasingly important role in computational geometry and topology. A key ingredient in the design of efficient algorithms on such surfaces is the availability of a geometric discretization of controlled complexity. In this paper, we present the first algorithm for constructing e-nets on hyperbolic surfaces starting from a fundamental polygon representation. Our approach is based on Delaunay refinement and relies on maintaining Delaunay triangulations through edge flips. The size of an e-net cannot be bounded solely as a function of the genus because of the presence of arbitrarily long collars around short geodesics. To overcome this difficulty, we introduce the notion of a pseudo e-net, which decomposes the surface into e-thin cylinders together with a Delaunay triangulation over an e-net of the remaining thick part. As applications, we obtain algorithms for computing the length spectrum of an e-thick hyperbolic surface and for computing the systole from a pseudo log(sqrt(2))-net. These results demonstrate that Delaunay-based discretizations provide a practical and versatile framework for algorithmic computations on hyperbolic surfaces.

In topological data analysis, in particular persistent homology analysis, extracting "optimal" representatives for homology classes is crucial for identifying geometric regions of interest. In prior work, optimality is defined in terms of minimizing length or volume. In this work, we restrict our attention to a single homology class in degree $1$ and introduce the total absolute curvature of cycles as the cost function. We show that this cost function, based on angles between edges of cycles, penalizes departures from planarity, convexity, and simple-ness of the cycle representative. We formulate the "angle-optimal homologous cycle problem", recast it as a binary quadratic optimization problem, and show the results of experiments on artificial toy data.

We prove that minimum Riesz $s$-energy subset selection in the Euclidean plane is NP-complete already for the fixed exponent $s=2$. To our knowledge, this is the first Euclidean hardness result for exact Riesz-energy subset selection in which both the ambient dimension and the exponent are fixed. The reduction uses Barahona's planar cubic Ising model with uniform field. A spin is encoded by one diagonal of a four-point square. Axis-aligned selector chains implement ferromagnetic consistency, while a $45^\circ$ terminal geometry yields an antiferromagnetic source interaction. Rational diagonal perturbations realize the magnetic field, and all remaining interactions are dominated by polynomial separation. Because $s=2$ and all coordinates are rational, every constructed energy and the decision threshold are rational exactly.

Triangle-based measures, commonly referred to as badness functions, are widely employed to quantify the extent to which a distance matrix deviates from an ideal geometric configuration. Different formulations of these functions may capture distinct facets of local non-uniformity, and their behavior is often influenced by the underlying distance metric chosen for evaluation. In practical settings, although a canonical badness function may be conceptually preferred, factors such as computational cost, algorithmic constraints, or data-specific characteristics frequently necessitate the adoption of modified versions-for instance, approximate forms or alternatives defined under different distance metrics. This gives rise to a central question: to what degree do these variants retain the structural consistency properties of their original counterparts? To address this issue, we develop a systematic correlation-based framework for evaluating structural consistency. As an illustrative instantiation of this framework, we compute badness sequences from a set of representative distance matrices alongside randomly generated triangle configurations, which are designed to cover variants that may arise under diverse practical scenarios. We then assess pairwise similarities among these sequences using four correlation coefficients. The experimental outcomes indicate that certain badness variants exhibit a notably high degree of structural consistency, whereas others reveal complementary behavioral patterns; moreover, the choice of distance metric exerts a considerable influence on the observed trends. These findings offer practical insights for the informed selection of distance metrics and triangle badness function variants in tasks including geometric reconstruction, triangulation, and structural analysis of pairwise distance data.

Deploying wireless nodes to maximize coverage area within a given region is an important challenge in wireless sensor networks, UAV path planning, base station placement and other industrial fields. This practical problem can be mathematically equivalent to an optimal circle covering problem. Although theoretical optimal configurations exist for simple cases in mathematics, the NP-hard nature of this problem makes it computationally prohibitive for complex polygons with numerous nodes. Existing approaches are usually designed for regular domains, while those applicable to irregular polygons often suffer from poor initialization, excessive coverage overlap and failure to constrain nodes within the boundary, leading to low coverage efficiency and long runtime. To address these issues, we propose an improved quasi-physical dynamic algorithm (IQPD) for wireless node deployment in arbitrary convex polygons. Our contributions are threefold: (1) proposing a structure-preserving initialization that maps a hexagonal close packing pattern into the target polygon via scaling and affine transformation, ensuring near-optimal initial node distribution; (2) constructing a refined virtual force model by incorporating friction and a radius-expansion optimization mechanism to reduce coverage area overlap; (3) developing a boundary encircling strategy leveraging normal and tangential gradients to reposition nodes deployed outside boundaries after initial optimization. Extensive experimental results demonstrate that our method consistently outperforms other new metaheuristic algorithms across diverse convex polygon shapes, including randomly generated data and real-world scenarios. Our method achieves the highest coverage rate and node utilization rate among all compared algorithms, greatly improving wireless coverage efficiency.