archive
Every paper Pith has read. Search by title, abstract, or pith.
90 papers in cs.CG · page 1
-
Meschers process impossible objects without cuts or bends
Meschers: Geometry Processing of Impossible Objects
-
Min-1-planarity testing is NP-hard
Min-1-Planarity is NP-Hard
-
LP rounding yields (1+2/e) approx for weighted segment hitting
Hitting Axis-Parallel Segments with Weighted Points
-
Multi-term error metric simplifies noisy meshes faster
Fast and Robust Mesh Simplification for Generated and Real-World 3D Assets
-
Hodge split isolates topology from geometry in neural field operators
Topology-Preserving Neural Operator Learning via Hodge Decomposition
-
Outer-k-string recognition is NP-hard for any fixed k
Two Results on Outer-String Graphs
-
k-d trees reduce nearest neighbor search to random guessing in high dimensions
Performance bounds for nearest neighbor search with k-d trees
-
FPT schemes give (1+ε) approximations for min-sum radii and diameters
FPT Approximation Schemes for Min-Sum Radii and Min-Sum Diameters Clustering
-
Diameter in plane intersection graphs depends on object type and value
Charting the Diameter Computation Landscape on Intersection Graphs in the Plane
-
Containment relations define higher-order persistence diagrams
Higher-order Persistence Diagrams
-
Deterministic algorithms cannot hit both time and I/O optima for convex hulls
The Impossibility of Simultaneous Time and I/O Optimality for The Planar Maxima and Convex Hull Problems
-
Nearly-tight bounds for vertical decompositions in 3D and 4D
Nearly-Tight Bounds for Vertical Decomposition in Three and Four Dimensions
-
Random slicing with NW smoothing speeds up topological optimization
Towards Scalable Persistence-Based Topological Optimization
-
Shortest tours for disjoint orthogonal polygons in subquadratic time
Touring a Sequence of Orthogonal Polygons
-
Subquadratic algorithm for shortest tours of disjoint polygons
Touring a Sequence of Orthogonal Polygons
-
Coordinated robot motion is FPT on polygon discretizations
Coordinated Motion Planning is FPT on Discretized Simple Polygons
-
Algorithm retrieves minimal points for imprecise Pareto fronts
Instance and Universally Optimal Bounds for Imprecise Pareto Fronts
-
GPU clipping scales 3D Voronoi diagrams to large uneven point sets
Scalable GPU Construction of 3D Voronoi and Power Diagrams
-
Geometry-aware test bounds simplicial network expressivity
Geometry-Aware Simplicial Message Passing
-
Algorithm approximates 2D curve warping within factor 5
A Constant-Factor Approximation for Continuous Dynamic Time Warping in 2D
-
Boundary registration plus quasi-conformal fill quantifies planar shape variation
Planar morphometry via functional shape data analysis and quasi-conformal mappings
-
Combined boundary and interior mapping improves planar shape analysis
Planar morphometry via functional shape data analysis and quasi-conformal mappings
-
Riesz energy point selection is NP-hard in the plane
On the Complexity of Minimum Riesz s-Energy Subset Selection in Euclidean and Ultrametric Spaces
-
Hull vertices in cyclic subsequence order cut convex hull to O(n sqrt(log n))
Computing Planar Convex Hulls with a Promise
-
Decomposition enables O(log n + k) visibility queries in O(n^{2+ε}) space
Visibility Queries in Simple Polygons
-
Exact d thresholds set for covering n+d triangles with n²+k small copies
Optimally Covering Large Triangles with Homothetic Unit Triangles
-
Zero sets of complex sections produce bijective surface maps
Implicit Minimal Surfaces for Bijective Correspondences
-
Recursive successor lists speed k-NN on manifolds by 1-10x
Manifold k-NN: Accelerated k-NN Queries for Manifold Point Clouds
-
Triangulation flip chain mixes in Õ(n²) time
Faster Mixing for Triangulations via Transport Flows
-
Greedy sweepline makes Jordan curve traversal maximal
A greedy maximal sweepline algorithm for a Jordan curve
-
Witness Set enters NP and XP for simple polygons
Witness Set: A Visibility Problem in $NP\cap XP$
-
Seven origami axioms now have explicit spherical equations
Spherical Geometrical Bases of Spherical Origami
-
Farthest-point Voronoi speeds rectangle disk queries
Smallest Enclosing Disk Queries Using Farthest-Point Voronoi Diagrams
-
Minimum span in upward-planar drawings is NP-hard for trees
Upward-Planar Drawings with Bounded Span
-
O(kn²) program selects optimal diversity subsets on lines
Exact Dynamic Programming for Solow--Polasky Diversity Subset Selection on Lines and Staircases
-
The paper claims to prove the Jordan curve theorem by generalizing the sweepline…
A proof of Jordan curve theorem based on the sweepline algorithm for trapezoidal decomposition of a polygon
-
Nesting Bird Box problem is ER-complete
The Nesting Bird Box Problem is ER-complete: Sharp Hardness Results for the Hidden Set Problem
-
Nesting Bird Box problem is ER-complete
The Nesting Bird Box Problem is ER-complete: Sharp Hardness Results for the Hidden Set Problem
-
Fat object graphs allow 2 to n to the 1-1/(d+1) algorithms for some hard problems
Small Independent Sets versus Small Separator in Geometric Intersection Graphs
-
Stellated tetrahedron fails Rupert test in over 88% of orientations
A stellated tetrahedron that is probably not Rupert
-
Calibrated tests detect collapse in high-dim point clouds
Calibrated Persistent Homology Tests for High-dimensional Collapse Detection
-
Poncelet inversive circumcenter traces conic
Conic locus of inversive Poncelet circumcenter and two points of invariant circle power
-
Equal lengths for equivalent edges preserve symmetry in 3D graphic statics
Point Group Symmetry of Polyhedral Diagrams in Graphic Statics
-
Dynamic (1+ε)-spanner for disk graphs uses polylog updates
A dynamic $(1+\varepsilon)$-spanner for disk intersection graphs
-
Second gonality of aCM curves on quartics fixed by Clifford net
Second gonality of smooth aCM curves on quartic surfaces in $\mathbb{P}^3$
-
Fréchet distance in dD grids approximated in (n/ε)^{2-2/d} time
Near-tight Bounds for Computing the Fr\'echet Distance in d-Dimensional Grid Graphs and the Implications for {\lambda}-low Dense Curves
-
Mixed double-wedges yield Ω(n²) intersection regions
Bowties and Hourglasses: Intersections of Double-Wedges (or Stabbing and Avoiding Line Segments)
-
Shortest paths in pseudodisk graphs run in near-linear time
Single-Source Shortest Paths and Almost Exact Diameter in Pseudodisk Graphs
-
Online rule matches prophet's Voronoi cell within constant factor w.h.p
The Prophet and the Voronoi Diagram
-
Algorithm counts every lattice rectangle in n-by-n grid in O(n log^{2} n) time
Counting All Lattice Rectangles in the Square Grid in Near-Linear Time