35 papers
This paper generalizes decomposition methods for chirotopes to develop a precise asymptotic estimate for the number of triangulations of the double circle by applying functional equations and the kernel method.
This paper presents algorithms for recognizing subgraphs of regular tilings, proving that the problem is solvable in quasi-polynomial time for hyperbolic tilings, subexponential time for Euclidean tilings, and constant time for spherical tilings, while highlighting that the Euclidean case remains NP-hard even for trees.
This study introduces a computational framework combining Design-by-Morphing and Bayesian optimization to generate undulatory swimming profiles that achieve 16%–35% higher propulsive efficiency than traditional anguilliform and carangiform modes by optimizing kinematic parameters and redistributing energy through favorable surface stress distributions.
This paper generalizes the disk scaling model for graph modification by allowing rescaled disks to choose radii within a specific interval, establishing that the problem is in XP for any polynomially recognizable graph class while providing a detailed complexity landscape that includes NP-hardness and FPT results for cluster graphs, polynomial-time solvability for complete graphs, and W[1]-hardness for connected graphs.
This paper investigates improved lower and upper bounds for the minimum number of points required in a bichromatic planar set to guarantee the existence of specific monochromatic geometric structures, including the long-standing open problem of convex empty monochromatic quadrilaterals.
This paper addresses the challenge of minimizing energy consumption for drone air traffic control by proving the theoretical intractability of finding optimal sensor ranges for general coverage while presenting a practical geometric algorithm that efficiently solves the peak-power minimization variant in real-time.
This paper investigates the structural properties of shortest flip sequences between plane spanning trees on point sets in convex position, confirming the validity of the "parking edge" and "reparking" conjectures in specific cases while disproving them in the general setting.
This paper investigates the computational complexity of multi-robot motion planning for sliding square robots with a constant move limit, demonstrating that the problem remains NP-hard in most scenarios except when the squares are unit-sized and the target configuration is unlabeled.
This paper presents an optimal time algorithm for computing the faces in a line arrangement that contain at least one point from a given set, matching the known lower bound and resolving a problem open since 1988.
This paper establishes a unified framework linking quadratic polarities to deformed Legendre transformations via linear algebra on homogeneous coordinates, defines polar divergences that generalize Fenchel-Young and Bregman divergences, and elucidates the reference duality in information geometry through total polar Fenchel-Young divergences.
This paper addresses the computational challenges of generalizing fair top- selection to multiple protected groups while minimizing disparity from a reference function, revealing new hardness barriers for small and proposing an efficient, robust two-pronged solution that incorporates utility loss as an alternative disparity measure.
This paper resolves the open question regarding the parameterized complexity of the Optimal Morse Matching problem by presenting a $2^{O(k \log k)} n$-time algorithm for bounded-treewidth complexes and proving its optimality under the Exponential Time Hypothesis.
This paper investigates the conditions under which pairwise disjoint curves are unavoidable or avoidable in complete graph drawings, characterizing the resulting plane structures based on specific crossing rules for adjacent and non-adjacent curves.
This paper investigates the limitations of plane substructures in drawings of the -dimensional hypercube graph by constructing drawings with restricted plane paths, matchings, and subgraphs, while also establishing existence guarantees for specific rectilinear configurations and characterizing universal plane subgraphs as forests of caterpillars.
This paper proposes a fast and provably correct method for approximating the persistence diagrams of sliding window embeddings of quasiperiodic functions by integrating the Three Gap Theorem from number theory with the Persistent Künneth formula from topological data analysis.