Uniform Capacitated Clustering with Few Extra Centers
Kangke Cheng, Guanlin Mo, Hu Ding
AI 速览：研究在允许开放 k+⌊εk⌋ 个中心且严格满足容量约束下，均匀容量 (k,z)-聚类的近似算法。
In uniform capacitated $(k,z)$-clustering, we open $k$ centers and assign every client to a center so that no center serves more than $U$ clients, minimizing the sum of the $z$-th powers of the assignment distances; $k$-median and $k$-means are the cases $z=1$ and $z=2$. We study algorithms that may open $k+\lfloor\varepsilon k\rfloor$ centers for a fixed $\varepsilon\in(0,1]$ and must respect the capacities exactly. In low dimensions, we give deterministic algorithms that are, except for $k$-median in the plane, the first polynomial-time algorithms with $(1+\varepsilon)k$ centers whose ratio is bounded independently of $\varepsilon$. In Euclidean space of any dimension, with clients of bounded doubling dimension, the ratio is $\mathcal{B}_z-(\mathcal{B}_z-1)\varepsilon+δ$ for every fixed $δ>0$, where $\mathcal{B}_z<3^z$ for $z>1$; this is $3-2\varepsilon+δ$ for $k$-median and $5-4\varepsilon+δ$ for $k$-means. In doubling metrics, the ratio is $3^z-(3^z-1)\varepsilon+δ$ when centers may share a location, and a constant otherwise, such as $\min\{7-4\varepsilon,\,3+2\ln(1/\varepsilon)\}+δ$ for $k$-median. In general metrics, deleting centers greedily gives ratio $3+2\ln(1/\varepsilon)+δ$ for $k$-median when centers may share a location and $7+2\ln(1/\varepsilon)+δ$ otherwise, improving the previous $O(\varepsilon^{-2}\log(1/\varepsilon))$. Our main tool is a rescue lemma. Splitting a near-optimal uncapacitated solution gives at most $2k-1$ blocks of at most $U$ clients, and giving a block a private center saves its share of the extra cost of following an optimal solution. Since a center of the optimal solution can be closed once all its blocks are rescued, $\lfloor\varepsilon k\rfloor$ extra centers save almost an $\varepsilon$-fraction of this extra cost instead of an $\varepsilon/2$-fraction.
Prabhu Nithin Gollapudi, Andreas Maier, Franziska Mathis-Ullrich, Water Zhao, Jia Wang, Siming Bayer
In the context of multi-stage trajectory planning for robotic percutaneous liver interventions, identifying a kinematically feasible entry point remains a critical computational bottleneck. Existing methods rely on exhaustive inverse kinematics or randomized searches, incurring delays of 13 to 27 seconds per target and limiting real-time intraoperative adaptation. This paper introduces an Orientation-Based Reachability Map (ORM) that precomputes the kinematic feasibility of a 6 Degrees of Freedom (DoF) serial manipulator across 188,873 workspace positions and encodes orientation feasibility into a compact, indexed 83 MB map. A Just-In-Time (JIT) compiled runtime pipeline replaces live optimization with near-instantaneous array lookups. Experimental evaluation demonstrates a reduction in planning latency from 13.5-26.9 s to 0.289-0.349 s per target while maintaining high geometric fidelity, achieving a mean convex hull volume overlap ratio of 0.933 and a mean alpha-shape volume ratio of 0.976 relative to the baseline reachable point cloud. The proposed ORM framework enables sub-second entry point planning and provides an efficient computational framework for robotic needle insertion in percutaneous liver ablation.
Yuta Inoue, Ken-ichi Kawarabayashi, Atsuyuki Miyashita, Bojan Mohar, Carsten Thomassen, Mikkel Thorup
The famous Four Color Theorem (4CT) states that any planar graph can be colored with four colors, but how do we find a 4-coloring? In our previous paper [FOCS'26], we presented a simple combinatorial algorithm to 4-color planar graphs in $O(n\log n)$ time. We improve it here to $O(n)$ time, which is optimal. The algorithm from our previous paper is based on proving that every planar triangulation has a linear number of reducible configurations or obstructing cycles. The bottleneck for the algorithm is that we need $O(\log n)$ Kempe changes to extend a recursive 4-coloring to the reducible configurations. Each Kempe change can involve a constant fraction of the graph and takes linear time. Here we show that all $O(\log n)$ Kempe changes can be identified and implemented in $O(n)$ time. The idea is to spend $O(n)$ time to preprocess the graph so that we can identify and simulate each good Kempe change in $O(n/\log n)$ amortized time. Thus, we implement all $O(\log n)$ Kempe changes in $O(n)$ total time. Based on this, we implement the whole 4-coloring in linear time. We note that creating such a representation for fast identification and simulation of the right Kempe changes is a challenge of data structures, unlike the previous paper that builds on a new graph theoretic understanding of reducible configurations.
Hard min/max operations preserve the sign of exact implicit solids but generally destroy signed-distance semantics. Arbitrarily small, sign-preserving value perturbations can rotate the normalized gradient by nearly a right angle and displace a gradient-projected boundary witness by a finite amount. We formalize this as the absence of a value-only stability modulus for witness projection. We introduce a witnessed Boolean contract checking value and gradient errors, positive reach, active-branch separation, and a Lipschitz visibility margin at the approximate witness. A sharp normalization lemma bounds the normal-direction error. An enlarged neighborhood permits transfer of the inactive operand's bound between the approximate witness and the true foot point. Under the stated analytic and domain assumptions, passing the checks identifies a true point on the union boundary and bounds distance deficiency by the active operand's pointwise value error. Failed or unavailable checks return Unknown. The argument extends to finite hard unions by testing every inactive operand. An executable proof-chain audit finds no violations on 75,738 certified samples. A broader analytic stress test covers spheres, capsules, ring tori, three Boolean operators, and a four-leaf union. Of 96,000 narrow-band samples, 87,469 pass with zero oracle violations; per-case coverage ranges from 72.67% to 98.30%. Removing visibility admits 75 truly invalid witnesses, showing that branch separation alone is insufficient. Non-union cases remain empirical tests, not new theorems.
Population displacement is a housing-related involuntary residential dislocation. It has become increasingly widespread in many cities, particularly in neighbourhoods undergoing rapid economic and demographic change, and measuring it is essential to assess the social consequences of urban transformation and housing market pressures. Despite its relevance, quantifying displacement presents difficulties due to limited replicability across cities and time periods and the need to analyse long time spans: displacement is a gradual process, impossible to capture in one data snapshot. We introduce a novel tool to overcome these difficulties. Using publicly available address change data, we construct four cubical complexes simultaneously incorporating geographical and temporal information of people moving, and analyse using Topological Data Analysis tools. Finally, we demonstrate this method through a 20-year case study in Madrid, Spain. The results demonstrate its ability to reveal patterns consistent with population displacement and identify the neighbourhoods and years potentially affected--patterns not observable from yearly maps of the raw address change data.
Given n points and $ε>0$, a well-separated pair decomposition (WSPD) is a collection of dumbbells {X,Y}, where X and Y have diameter at most $ε$ times their distance, such that every pair of points has one point in X and the other in Y for some dumbbell. A partition WSPD covers every pair exactly once, and a cover WSPD at least once. Callahan and Kosaraju give a partition WSPD with $O(n/ε^d)$ dumbbells in $R^d$, but many point sets have far smaller WSPDs of both kinds. For $d\ge2$, the known $O(1)$-approximations of the minimum size WSPD that preserve the separation $ε$ have unspecified factors, above $10^7$ for $d=2$ by our estimates. For cover WSPDs, we give an $O(n^2\log n)$-time sweep approximation algorithm with a factor 40 in the plane for $ε\le1/16$. It extends to $R^d$ with a factor $2^{O(d)}$. The sweep is also a lower-bound tool: its number of steps is a lower bound on the WSPD size. For partition WSPDs, we analyze quadtree and fair split tree constructions: in the plane and for $ε\le1/5$, they give constant approximation factors, the smallest of which is 252 for a randomly shifted and scaled quadtree. In experiments with $ε=1/20$, the number of sweep steps is at least 0.91 OPT for n = 500, where the optimum OPT is known, and a local search raises it to a lower bound of 0.99 OPT. A greedy variant of the sweep, which is still a certified 40-approximation, is at most 1.28 times the lower bound for n = 10000. Followed by a new local-search heuristic that shrinks the WSPD, it is within 0.02% of the optimum on every instance with n = 500, and at most 1.10 times the lower bound for n = 10000. We then show how to convert the cover WSPDs into partition WSPDs. For n = 10000, the conversion gives on average 1.13 times the lower bound, against 1.05 for the cover WSPD itself and 1.55 for the Callahan-Kosaraju partition WSPD.
Peter D. Sharpe, Corey Adams, Negin Sobhani, Sanjay Choudhry
PhysicsNeMo-Mesh is the mesh module of the open-source PhysicsNeMo library. It provides mesh processing similar to PyVista, but on the GPU, in batches, and inside PyTorch's automatic differentiation. Like xarray for unstructured meshes, it attaches semantics to data: fields on points, cells, and whole meshes have names and shapes, and a simulation case keeps the complete PDE problem specification, including boundary conditions and their prescribed values. It addresses three problems that plague machine learning for physical simulation. First, GPU utilization is bottlenecked by I/O, because samples are very large relative to the compute per forward pass. Second, because traditional preprocessing is expensive, it is necessarily done once, during curation, rather than differently for each model and workflow at the point of use. Finally, advanced equivariant and mesh-native architectures require information that curation ordinarily discards. Fast GPU mesh processing makes it practical to preprocess at the point of use: on one GB200 GPU, mesh operations run $6.2\text{--}1{,}068\times$ faster than VTK with 72 threads, and loading a whole case is $8.0\text{--}88\times$ faster than reading its VTK files ($8.0\times$ when both read the same fields). Overlapped with training, this preprocessing costs $2.1\%$ of throughput for a $127\,\text{ms}$ Transolver step. So one dataset serves many models and workflows: in PhysicsNeMo's public recipe, one stored DrivAerML dataset feeds Transolver, GeoTransolver, and GLOBE. PhysicsNeMo-Mesh combines the speed of an intermediate array store with the flexibility of an archival format such as VTK. When shapes and wall conditions both vary, per-boundary conditions cut a heat-conduction error from $87\%$ to $6\text{--}9\%$. And by keeping field ranks and named boundaries, it retains the semantic structure that next-generation architectures will need.
The min-sum $k$-clustering problem asks to partition an input of $n$ points into $k$ clusters so as to minimize the total pairwise distance within clusters. It is a natural alternative to center-based objectives when the data is not well captured by a small set of representative points. We study for this problem two standard sketching methods, dimension reduction and coresets, which represent the input more compactly while preserving the min-sum cost of every $k$-partition up to $1\pm\varepsilon$ factor. Our first contribution addresses dimension reduction in Euclidean space. The Johnson-Lindenstrauss (JL) Lemma readily implies that a random linear map to target dimension $t=O(\varepsilon^{-2}\log n)$ preserves, with high probability, the min-sum cost of all $k$-partitions. We show that target dimension $t=O(\varepsilon^{-2}(ddim\cdot\log(1/\varepsilon)+\log k+\log\log n))$ suffices for Euclidean inputs of doubling dimension at most $ddim$, and moreover this bound is nearly optimal. We also show that target dimension $t=O(\varepsilon^{-2}(\log(1/\varepsilon)+\log k+\logΔ))$ suffices for Euclidean inputs of aspect ratio at most $Δ$. Our second contribution is to design the first $\varepsilon$-coreset for metric min-sum $k$-clustering. It is actually a movement-based coreset, has size $(1/\varepsilon)^{O(ddim)} k\log n$ for inputs of doubling dimension at most $ddim$, and can be constructed in randomized near-linear-time. We further use these coresets to design streaming algorithms for the problem.
Call a finite nonempty point set $S\subset\mathbb{R}^d$ all-even if for every direction $\ell \in \mathbb{P}(\mathbb{R}^d)$, the number of hyperplanes perpendicular to $\ell$ that intersect $S$ is even. In 2026, Francisco Santos presented a question of Juan Benigno Seoane-Sepúlveda on the existence of all-even sets in dimensions $3$ and higher, together with examples of such sets in dimension $2$. Call a set $S\in\mathbb{R}^d$ line-all-even if for every direction $\ell \in \mathbb{P}(\mathbb{R}^d)$ the number of lines parallel to $\ell$ that intersect $S$ is even. As Santos pointed out, every all-even set in $\mathbb{R}^3$ is line-all-even. We conjecture that there exist no line-all-even sets in $\mathbb{R}^3$ that affinely span $\mathbb{R}^3$ We show that our conjecture is equivalent to the statement that every planar all-even set satisfies a certain property, which we call height-rigidity. This property has a natural interpretation in linear algebra terms. Furthermore, we present a hierarchy of properties of planar point sets that imply height-rigidity. We construct several all-even sets in the plane, including some infinite families, and show that all the sets we constructed are height-rigid. In addition, we prove that every all-even set in the plane that can be covered by six or fewer parallel lines is height-rigid.
We give the first explicit constant for crossing families of linear size by showing that every set of $n$ points in general position in the plane contains a crossing family of size approximately $\frac{n}{79}$. We further identify some conditions where there are even larger crossing families. The first such condition forbids the existence of a large different pattern, namely non-convex 4-clusters: We show that every point set contains either a large non-convex 4-cluster or a large crossing family. The second condition is the existence of many crossings: We give a bound for the size of a crossing family in terms of the number of crossings of the complete geometric graph drawn on the point set.
Sarita de Berg, Joachim Gudmundsson, Peter Kramer, Christian Rieck, Sampson Wong
We investigate coordinated motion planning (CMP) for unit square robots in the plane under the $L_1$ metric. Given two arrangements of $k$ robots, we seek a movement schedule minimizing one of three objectives: the Min-Sum objective (sum of distances), the Min-Makespan objective (latest time of arrival) and the Min-Exposure objective (a new objective). For Min-Sum and Min-Makespan, we provide a simplified approach and improved bounds, compared to Eiben, Ganian and Kanj (SoCG 2023). To this end, we partition the configuration space based on the relative ordering of the robots. This leads to a simple and efficient framework to discretize the search space. Our results extend to several settings in the plane, including convex robots in convex domains and vertex robots in rectangular grids. Finally, we apply our results to the new Min-Exposure objective. Given a set of polygonal regions that provide cover, the task is to find a schedule with minimal elapsed time during which at least one robot is not fully covered. We give an $\mathcal{O}(n^4\log n)$ time algorithm that computes exposure-minimal schedules for $k=2$ robots, and an XP algorithm for arbitrary $k$.
The diagonals of a regular pentagon dissect it into eleven pieces and draw a pentagram; the dodecahedron dissected by the twelve face planes of its inner core gives Kramer's seven "elementary cells" of 1982. We define the stellation dissection of a golden regular polytope in any dimension as the dissection of the convex hull of its final regular stellation by the facet hyperplanes of the core, show that the core has phi^(-d) of the inradius of the hull for d = 2, 3, 4, and carry the dissection out for the first time on the 120-cell. The foundation is the arithmetic of the golden ring Z[phi], the ring of integers of Q(sqrt 5): vertices and hyperplanes live in Z[phi]^d, every orientation test is the exact sign of an element of Z[phi], decided with integers, and the pieces are named by sign vectors. We develop this foundation from scratch (conjugation, norm, units, the primes sqrt 5, 2, 3, the exact sign test, the lattice x -> (x, conj x), the vertex modules of the dodecahedron and the 120-cell, the icosian ring) and let it carry the geometry. The definition bifurcates in dimension four: the star cut at depth phi^(-4), a unit, has 2,455,201 cells in 338 orbits of H4; the hereditary cut at depth 1 - phi^(-4) = sqrt 5 / phi^2, a unit times the ramified prime, induces the three-dimensional dissection on every facet and has 8,161 cells in 8 orbits. New here: all vertices of the dodecahedral and of the hereditary dissection lie in the vertex module of the polytope being cut, whereas the star cut needs the denominators 2, 3 and 5; the seven kinds of pieces of the dodecahedron are exactly the I_h-orbits of sign vectors, with stellation layer equal to the number of plus signs. We catalogue the four-dimensional pieces and treat the circumscribed disc, ball and 4-ball. Every number quoted is recomputed exactly by a script whose output is reproduced in an appendix.
Given an arrangement of $\{1,\dots,n^2\}$ in an $n\times n$ grid, we lift each cell to $\mathbb{R}^3$ by centring its grid coordinates $(x,y)$ at the origin and taking its centred entry $z = s_{ij} - (n^2+1)/2$ as a vertical height. The convex hull of these $n^2$ points is the gem of the arrangement, whose lower and upper boundaries are the regular subdivisions of the grid induced by $\pm z$. While random arrangements and generic linear magic squares have gems whose vertex counts grow with $n$, our main theorem shows that the classical Siamese (de la Loubère) magic square of every odd order $n\ge5$ has $f$-vector $(12,26,16)$, isometry group $\{\pm\mathrm{id}\}$, and only the twelve vertices forced by the boundary of the grid. The proof shears the lift onto five horizontal terraces and reduces the hull calculation to a finite table of polynomials in $m=(n-1)/2$; the same method gives $f$-vector $(12,24,14)$ for the base-$n$ digit-exchanged square. Along any family of linear squares with fixed steps the $f$-vector is eventually periodic in $n$, whereas over all linear magic squares of prime order $n$ the maximum vertex count grows as $Θ(\ln n)$. Whenever the heights have vanishing first moments, a short principal-axes argument shows that the point set has a non-trivial isometry if and only if the arrangement is self-complementary up to dihedral symmetry. An exact census of the $880$ magic squares of order four yields $616$ congruence classes and $352$ combinatorial types of gems, and shows that while vertex and facet counts are nearly insensitive to the magic line-sum conditions, the volume and solid centroid shift systematically.
Fairness in clustering has attracted sustained research interest, motivated by the need to ensure equitable representation of protected groups in machine learning applications. We study fair $k$-means clustering in Euclidean space, where the proportion of each protected group in every cluster must lie within specified lower and upper bounds. These constraints make it challenging to determine both cluster centers and point assignments. Our algorithm first splits the input into many small fair clusters and then merges them into $k$ clusters with a weighted $k$-means algorithm. The merge is cheap only when the small clusters do not move points away from their optimal centers, so we add a displacement penalty to the split, which charges each point for how far the small clusters move it. Given a $ρ$-approximate algorithm for weighted $k$-means and any $ε>0$, our algorithm returns a fractional solution whose cost is at most $3ρ+ε$ times the optimal integral fair cost. With a PTAS as the subroutine, the approximation ratio becomes $3+O(ε)$, improving the previous factor of $5+O(ε)$. This ratio is the best possible: unless P=NP, no polynomial-time algorithm achieves the ratio $3-δ$ for any fixed $δ>0$, even in one dimension. The solution satisfies all fairness constraints exactly and can be rounded to an integral assignment with a bounded additive violation of fairness and no increase in cost. The same approximation guarantee extends to the $k$-sparse Wasserstein barycenter problem.
The spatial chromatic model (SCM) is a novel entity-oriented spatial data model proposed in recent years. Spatial tessellations formed by SCM have been applied in preliminary analyses of spatial point pattern recognition,spatial topology, and Voronoi diagram generation. Unlike previous spatial tessellation models, a key feature of SCM is that each subspace (cell) possesses a chromatic code, which serves as the foundation for various theoretical analyses and applications of SCM. The uniqueness of cell cluster codes in SCM constitutes an important property of the model. Previous studies have demonstrated the uniqueness of the chromatic codes of 2-cell and 3-cell connected disjoint clusters. Building on this analysis of connected cluster code characteristics, this paper proves the uniqueness of the chromatic codes of 4-cell connected disjoint clusters. The proof results and the new concepts introduced in this study help further refine the spatial chromatic model and provide a theoretical foundation for its subsequent applications.
It remains unknown if every prismatoid has a nonoverlapping edge-unfolding, a special case of the long-unsolved "Dürer's problem." Recently nested prismatoids have been settled [Rad24] by mixing (in some sense) the two natural unfoldings, petal-unfolding and band-unfolding. Band-unfolding fails due to a specific counterexample [O'R13b]. The main contribution of this paper is a characterization when a band-unfolding of a nested prismatoid does in fact result in a nonoverlapping unfolding. In particular, we show that the mentioned counterexample is in a sense the only possible counterexample. Although this result does not expand the class of shapes known to have an edge-unfolding, its proof expands our understanding in several ways, developing tools that may help resolve the non-nested case.
Let $P$ be a polytope defined by the system $A x \leq b$, where $A \in R^{m \times n}$, $b \in R^m$, and $\text{rank}(A) = n$. We give a short geometric proof of the following tight upper bound on the number of vertices of $P$: $$ n! \cdot \fracΔ{Δ_{\text{average}}} \cdot \text{vol}(B_2) \sim \frac{1}{\sqrt{πn}} \cdot \left(\frac{2 π}{e}\right)^{n/2} \cdot n^{n/2} \cdot \fracΔ{Δ_{\text{average}}}, $$ where $Δ$ is the maximum absolute value of $n \times n$ subdeterminants of $A$, and $Δ_{\text{average}}$ is the average absolute value of subdeterminants of $A$ corresponding to a triangulation of $P$'s normal fan. Assuming that $A$ is integer, such polyhedra are called $Δ$-modular polyhedra. Note that in the integer case, the bound can be simplified via the inequality $Δ_{\text{average}} \geq Δ_{\min} \geq 1$, where $Δ_{\min}$ is the minimum absolute value of subdeterminants of $A$ corresponding to feasible bases of $A x \leq b$. For this, we prove and use a symmetric variant of Macbeath's theorem. Additionally, we give a direct argument based on prior results in the field, showing that the graph diameter of $P$ is bounded by $O\bigl(n^3 \cdot \fracΔ{Δ_{\min}} \cdot \ln (n \fracΔ{Δ_{\min}}) \bigr)$. Thus, both characteristic of $P$ are linear in $Δ/Δ_{\min}$. From an algorithmic perspective, we demonstrate that: Given $A \in Q^{m \times n}$, $b \in Q^m$, and an initial feasible solution to $A x \leq b$, the convex hull of $P$ can be constructed in $O(n)^{n/2} \cdot m^2 \cdot \fracΔ{Δ_{\text{average}}}$ operations. For simple polyhedra, the dependence on $m$ reduces to linear; Given $A \in Z^{m \times n}$ and $b \in Q^m$, the number $|P \cap Z^n|$ can be computed in $O(n)^n \cdot \frac{Δ^4}{Δ_{\text{average}}}$ arithmetic operations.
The article is devoted to the construction of dimension-raising maps of cubes with the highest possible Holder exponent. In particular, a square-to-cube mapping with a Holder exponent of $2/3$ is constructed, which is a solution to the V.I.Arnold problem.
We study the \emph{Polynomial Avoidance Problem}: given a finite collection $F \subseteq Z[x_1,\dots,x_n]$ of nonzero polynomials, find a vector $x \in Z^n$ of minimum $\ell_p$-norm such that $f(x)\neq0$ for every $f \in F$. Each polynomial is given sparsely as a list of its nonzero terms. The affine special case is the \emph{Hyperplane Avoidance Problem}. This special case arises in Barvinok-type algorithms for counting integer points in polyhedra, when certain rational generating functions must be evaluated at a removable singularity. Our main results are as follows: 1) Let $D:=\sum_{f\in F} \text{deg} f$. Every instance admits a feasible vector $x$ satisfying \[ \|x\|_1 \leq \min\left\{D,\frac{D+n}{2}\right\}. \] This bound is tight. Such a vector can be found by a deterministic algorithm whose bit complexity is polynomial in $D$ and the sparse encoding length of the input. Our proof uses a new algorithmic variant of the \emph{Combinatorial Nullstellensatz}; 2) In the affine case, with $m$ input polynomials, such a vector can be constructed by a fast deterministic polynomial-time algorithm using $O(nm)$ arithmetic operations. For the homogeneous case, Barvinok's original approach provides only the weaker guarantee $\|x\|_1 = O((nm)^{n-1})$; 3) The problem is NP-hard for every $p\in R_{\geq 1}\cup\{\infty\}$, even for homogeneous linear forms; 4) As an application, we improve the complexity bound for counting integer points in general rational polytopes. We also improve the bound for polyhedra of bounded codimension; this includes the counting version of the \emph{Unbounded Subset-Sum} problem as a special case.
Yunpeng Lyu, Chao Cao, Ji Zhang, Howie Choset, Zhongqiang Ren
Routing problems such as Hamiltonian Path Problem (HPP), seek a path to visit all the vertices in a graph while minimizing the path cost. This paper studies a variant, HPP with Probabilistic Terminals (HPP-PT), where each vertex has a probability representing the likelihood that the robot's path terminates there, and the objective is to minimize the expected path cost. HPP-PT arises in target object search, where a mobile robot must visit all candidate locations to find an object, and prior knowledge of the object's location is expressed as vertex probabilities. While routing problems have been studied for decades, few of them consider uncertainty as required in this work. The challenge lies not only in optimality ordering the vertices, as in standard HPP, but also in handling history dependency: the expected path cost depends on the order in which vertices were previously visited. This makes many existing methods inefficient or inapplicable. To address the challenge, we propose a search-based approach RPT* with solution optimality guarantees, which leverages dynamic programming in a new state space to bypass the history dependency and novel heuristics to speed up the computation. Building on RPT*, we design a Hierarchical Autonomous Target Search (HATS) system that combines RPT* with either Bayesian filtering for lifelong target search with noisy sensors, or autonomous exploration to find targets in unknown environments. Experiments in both simulation and real robot show that our approach can naturally balance between exploitation and exploration, thereby finding targets more quickly on average than baseline methods.
Saul D. Freedman, Melissa Lee, Dragan Marušič, Tomaž Pisanski
Given a finite graph $G$, we characterize the automorphisms and automorphism groups of $G$ that can be realized as geometric symmetries and symmetry groups of straight line drawings of $G$ in the plane. In doing so, we correct a previous version of this characterization from the literature. As an application, we show that the graphs recently constructed by the first two authors to disprove the Polycirculant Conjecture, which have orders $16{,}464^k$ for each positive integer $k$, are the first known vertex-transitive graphs with no non-trivial realizable geometric symmetries. We also construct infinite families of graphs that exhibit all possible kinds of geometric symmetry.
Sebastian Haslebacher, Jonas Lill, Patrick Schnider, Simon Weber
We prove that an $ε$-approximate fixpoint of a map $f:[0,1]^d\rightarrow [0,1]^d$ can be found with $\mathcal{O}(d^2(\log\frac{1}ε + \log\frac{1}{1-λ}))$ queries to $f$ if $f$ is $λ$-contracting with respect to an $\ell_p$-metric for some $p\in [1,\infty)\cup\{\infty\}$. This generalizes a recent result of Chen, Li, and Yannakakis [STOC'24] from the $\ell_\infty$-case to all $\ell_p$-metrics. Previously, all query upper bounds for $p\in [1,\infty) \setminus \{2\}$ were either exponential in $d$, $\log\frac{1}ε$, or $\log\frac{1}{1-λ}$. Chen, Li, and Yannakakis also show how to ensure that all queries to $f$ lie on a discrete grid of limited granularity in the $\ell_\infty$-case. We provide such a rounding for the $\ell_1$-case, placing an appropriately defined version of the $\ell_1$-case in $\textsf{FP}^{dt}$. To prove our results, we introduce the notion of $\ell_p$-halfspaces and generalize the classical centerpoint theorem from discrete geometry: for any $p \in [1, \infty) \cup \{\infty\}$ and any mass distribution (or point set), we prove that there exists a centerpoint $c$ such that every $\ell_p$-halfspace defined by $c$ and a normal vector contains at least a $\frac{1}{d+1}$-fraction of the mass (or points).
Hadley Black, Arya Mazumdar, Barna Saha, Geelon So
This work establishes the query complexity of learning high-dimensional boxes in the exact query learning setting. Let $X \subset \mathbb{R}^d$ be a set of $n$ points, labeled by a collection of $k$ boxes: the label of each point in $X$ is determined by the unique box containing it. A learner aims to exactly recover the labels for every point in $X$ given access to a label oracle. We consider three increasingly-structured settings. In the most general setting, there are no conditions on the boxes, and they may overlap. We show that CAL (Cohn-Atlas-Ladner 1994), a classical active learning algorithm, is minimax-optimal with query complexity $Θ(kd \log (n/kd))$. When the boxes are disjoint, we examine two regimes. In the large-$k$ regime, CAL remains minimax-optimal. For the constant-$k$ regime, an optimized variant of the Halving algorithm (Hegedüs 1995) can beat CAL by a $\log(d)$ factor. Finally, in the most-structured settings, the boxes correspond to the leaves of a constant-sized decision tree. We prove a tight query complexity of $Θ(d + \log n)$ that is additive in $d$ and $\log n$, generalizing a recent result (Black-Larsen-Mazumdar-Saha-So 2026) that establishes the query complexity of learning decision stumps.
Given a fixed straight-line drawing of a complete graph, we seek a two-colouring of its edges that minimizes monochromatic crossing pairs. We prove that the threshold decision problem is NP-complete, even for points in general position with integer coordinates. Thus exact minimization is NP-hard, resolving the complexity question posed at the Crossing Number Workshop in 2019. We reduce from MaxCut on permutation graphs by representing source vertices with classes of geometric edges, whose crossings encode source adjacencies. The complete target also contains every other edge between its points, and their freely chosen colours can affect the encoded cost. To control these interactions, we construct a large comparison grid with two stable colour phases and use program points to turn this reference into colour preferences on other edges. The optimum differs from a computable baseline plus the amplified minimum number of uncut source edges by an error small enough to distinguish consecutive source values. The reduction is deterministic, with polynomially many points and polynomial coordinate bit length.
Sparse-view 4D reconstruction is highly under-constrained when only a few cameras are available. Generative priors can recover missing appearances, but video models are computationally impractical for iterative reconstruction, whereas single-view models produce temporally inconsistent pseudo-observations. Moreover, directly absorbing uncertain generative outputs into Gaussian optimization often creates redundant primitives and floating artifacts. To address these challenges, we propose DUET4D, a self-corrective coupled guidance framework for sparse-view 4D Gaussian splatting. The core of our approach is a self-corrective framework where the 4D representation guides generative prior for spatio-temporal consistent supervisions. We first construct sequential alignments from current Gaussian evidence to steer the latent restoration. Then we use Sequential Fidelity Resampling to lift generative supervisions into Gaussian space to selectively distinguish repeatedly supported primitives. The corrected representation then provides more reliable Gaussian evidence for the next restoration cycle. Extensive experiments demonstrate that DUET4D significantly improves rendering quality and rendering efficiency.
We study the following range searching problem in high-dimensional Euclidean spaces: given a finite set $P\subset \mathbb{R}^d$, where each $p\in P$ is assigned a weight $w_p$, and radius $r>0$, we need to preprocess $P$ into a data structure such that when a new query point $q\in \mathbb{R}^d$ arrives, the data structure reports the cumulative weight of points of $P$ within Euclidean distance $r$ from $q$. Solving the problem exactly seems to require space usage that is exponential to the dimension, a phenomenon known as the curse of dimensionality. Thus, we focus on approximate solutions where points up to $(1+\varepsilon)r$ away from $q$ may be taken into account, where $\varepsilon>0$ is an input parameter known during preprocessing. We build a data structure with near-linear space usage, and query time in $n^{1-Θ(\varepsilon^4/\log(1/\varepsilon))}+t_q^{\varrho}\cdot n^{1-\varrho}$, for some $\varrho=Θ(\varepsilon^2)$, where $t_q$ is the number of points of $P$ in the ambiguity zone, i.e., at distance between $r$ and $(1+\varepsilon)r$ from the query $q$. To the best of our knowledge, this is the first data structure with efficient space usage (subquadratic or near-linear for any $\varepsilon>0$) and query time that remains sublinear for any sublinear $t_q$. We supplement our worst-case bounds with a query-driven preprocessing algorithm to build data structures that are well-adapted to the query distribution.