35 papers
This paper improves the running time of -approximation algorithms for -median and -means clustering in low-dimensional Euclidean spaces to $2^{\tilde{O}(1/\varepsilon)^{d-1}} \cdot n \cdot \text{polylog}(n)1/\varepsilond$ is essentially optimal.
This paper presents Gap-ETH-tight randomized approximation schemes for the Traveling Salesperson Problem and Steiner Tree in -dimensional hyperbolic space with running time $2^{O(1/\varepsilon^{d-1})}n^{1+o(1)}$, achieved through a novel hybrid hyperbolic quadtree decomposition, non-uniform portal placement, and weighted crossing analysis.
This paper establishes that minimizing the longest edge length in a simultaneous geometric embedding of two paths on an integer grid is NP-hard, while providing an algorithm to minimize the grid perimeter when one path is -monotone and the other is -monotone.
This paper establishes that the diameter of the dual graph of an arrangement of topological disks is bounded by a function of and the maximum number of connected components in any pairwise intersection, providing a tight bound of for two disks and an bound for disks by analyzing the count of maximal faces.
This paper introduces a novel subgradient definition based on Busemann functions for convex optimization on Hadamard spaces, enabling the generalization of stochastic and incremental subgradient methods with guaranteed complexity bounds to nonpositively curved metric spaces such as BHV tree space.
This paper characterizes the conditions under which the band-unfolding of a nested prismatoid results in a nonoverlapping layout, demonstrating that the previously known counterexample is essentially the only obstruction to this method's success.
This paper establishes that the spanning ratio of the directed -graph is exactly 5, thereby closing the previously known gap between 4 and 7 and providing the first tight bound for any directed -graph.
This paper employs fine-grained complexity to analyze the computational hardness of minimizing the Hausdorff distance under translation, revealing intricate dependencies on dimensionality, the directed versus undirected nature of the distance, and the choice between continuous and discrete translation spaces, including asymmetric time complexities and conditional lower bounds that distinguish these variants.
This paper proposes a novel approach using persistent homology on a filtered witness complex to identify geographic gaps in cooling center coverage across four US cities, demonstrating that combining these topological findings with traditional heat vulnerability indices provides a more holistic assessment of heat-related mortality risk.
This paper investigates the computational complexity of extending fixed storyline layouts by inserting missing characters to minimize the local crossing number, proving the problem is W[1]-hard when parameterized by the number of inserted characters and active characters, but fixed-parameter tractable when parameterized by the sum of active characters and the local crossing number.
This paper proposes a topologically stable variant of the Hough transform for line detection in point clouds, which replaces the traditional discretized voting scheme with a continuous score function and utilizes persistent homology to identify candidate lines via an efficient algorithm.
This paper introduces permutation match puzzles on grids, characterizing their solvability via an acyclic constraint graph condition, providing a hook length formula for counting solutions, offering an algorithm for minimal repairs in the basic case, and proving that generalizing the problem to arbitrary permutations renders minimal repair NP-complete.
This paper analyzes a geometric balancing game on line arrangements, determining the minimum initial number of pebbles required for Alice to prevent Bob from emptying any box and proving that this threshold scales as for lines in general position.
This paper provides the first formal specification and comprehensive analysis of the Li-Chao tree, a widely used data structure in competitive programming, by establishing its algorithmic details, proving correctness, and evaluating its theoretical and empirical performance.
This paper investigates the non-injectivity of the verbose persistent homology transform (VPHT) for graphs with collinear vertices, identifying necessary and sufficient conditions for their non-reconstructibility to advance a complete classification of such cases.
This paper explores the geometry of popup structures by combining origami and kirigami principles to establish a design pipeline that uses discrete surface curvature definitions to generate cut-fold patterns capable of creating complex, deployable shapes with applications in drag reduction, packaging, and architecture.
This paper presents a highly efficient method for 3D point cloud neighbourhood searching that combines Space-Filling Curves with a linear Octree structure and specialized algorithms, achieving up to 10 faster performance and significant cache miss reductions compared to existing solutions while demonstrating strong parallel scalability.
This paper explores invariants of almost embeddings of graphs in the plane by establishing relations among them, connecting these to the homology of the deleted product, constructing examples, and presenting these topological concepts in an accessible manner while highlighting open conjectures.
This paper proposes a parameter-free, equivariant topological spatial graph coarsening method that reduces graph size by collapsing short edges while preserving key topological features through a novel triangle-aware graph filtration adapted from persistent diagrams.
This paper resolves an open problem by demonstrating that centralized reconfiguration of geometric amoebot structures using joint movements can be achieved in sublinear time, specifically rounds for transforming any structure into a canonical line segment and constant time for spiral-to-line conversions, without relying on auxiliary assumptions like metamodules.