Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

Computational Geometry

53 missions · 14 completed

Missions

Open39Completed14All53
🏆Completed
Convex OptimizationOptimization·Captain: mikedeng1

Rounding of Polytopes in the Real Number Model of Computation: Barycentric Coordinate Descent Finds a (1+ε)n-Rounding Ellipsoid of m Points in O(n(1/ε + ln n + ln ln m)) IterationsResearch Paper

Many algorithms for convex bodies need the body to be well rounded: sandwiched between two concentric ellipsoids whose size ratio is controlled by the dimension. The ellipsoid method, volume and integration algorithms, and preconditioning for linear programming use such roundings. For a polytope given by its vertices a1,…,am∈Rna_1,\dots,a_m \in \mathbb{R}^na1​,…,am​∈Rn, John's…

24 thms7 active users
Complexity TheoryMachine LearningOperations Research·Captain: Shuze Chen

Exact Euclidean k-Means: Faster in the Plane, Hard Beyond ItResearch Paper

Exact Euclidean k-means asks for the least possible sum of squared distances from data points to freely located centers. Two parameters shape the problem: the number of centers, k, and the ambient dimension, d. An algorithm whose exponent depends on their product can be polynomial for every fixed pair and still become impractical as either parameter grows.…

26 thms5 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

Demand Equilibria in Spatial Service Systems: At Locally Optimal Service Rates the Decentralized Demand Equilibrium Coincides with the Socially Optimal PartitionResearch Paper

Public and healthcare services — driver's licence offices, emergency rooms, testing sites — are spread over a region, and customers choose for themselves which facility to visit. A customer weighs two costs: the travel distance to a facility and the expected wait once there. The wait depends on how many other customers chose the same facility. The resulting…

12 thms5 active usersReviewed
Linear OptimizationOperations ResearchTheoretical Computer Science·Captain: mikedeng1

Linear Programming in Linear Time When the Dimension Is Fixed: Fixed-Dimension LP Feasibility Decided in Linear Time on the Real RAMResearch Paper

A linear program asks for a point x∈Rdx\in\mathbb{R}^dx∈Rd minimizing cTxc^TxcTx subject to nnn linear inequalities ∑j=1daijxj≥bi\sum_{j=1}^d a_{ij}x_j\ge b_i∑j=1d​aij​xj​≥bi​. Many problems in computational geometry and statistics are linear programs with few variables and very many constraints: separating two point sets by a line or plane, fitting a line in the Chebyshev (L∞L_\inftyL∞​) norm, finding the…

16 thms5 active usersReviewed
Convex OptimizationFunctional Analysis·Captain: mikedeng1

Deterministic Terminal Embedding with Optimal Target Dimension for Euclidean SpaceResearch Paper

A database of points can be reduced to fewer coordinates while approximately preserving distances among its stored points. Many geometric applications also compare those points with centers or queries supplied later. A guarantee only about pairs already in the database does not cover every such comparison. A terminal embedding asks for one map that…

26 thms4 active usersReviewed
CombinatoricsComplexity Theory·Captain: Shuze Chen

Hardness of Packing, Covering and Partitioning Simple Polygons with Unit Squares: 2×2 square packing is NP-hard for orthogonally convex grid polygonsResearch Paper

Packing problems ask how many copies of a shape fit, without overlap, into a container. One of the simplest is to decide whether kkk axis-aligned unit squares can be placed in a given polygon; scaling by two gives the equivalent problem 2 × 2-Square-Packing: given a polygon PPP and an integer kkk, decide whether PPP has room for kkk axis-aligned 2×22 \times 22×2 squares.…

23 thms4 active usersReviewed
Complexity Theory·Captain: Shuze Chen

Terrain Guarding is NP-Hard: NP-hardness of discrete and continuous terrain guardingResearch Paper

Selecting a small collection of sites with line of sight to an entire landscape is a geometric coverage problem. In the one-dimensional terrain model, the landscape is represented by a polygonal profile in the plane. The optimization question asks how many guards are needed to see every point of that profile. Applications motivating the model include road…

10 thms4 active usersReviewed
Complexity Theory·Captain: Shuze Chen

Orthogonal Terrain Guarding is NP-complete: NP-completeness of orthogonal terrain guardingResearch Paper

Terrain guarding asks how many observation sites are needed to see an entire landscape represented by a polygonal chain. The input specifies both the terrain and the number of guards available. A solution chooses observation sites whose combined visibility covers the whole landscape. Restricting the chain to horizontal and vertical edges simplifies its…

6 thms4 active usersReviewed
🏆Completed
Discrete GeometryTheoretical Computer Science·Captain: mikedeng1

An Optimal Algorithm for Approximate Nearest Neighbor Searching in Fixed Dimensions: Priority Search in a BBD-Tree Visits at Most ⌈1 + 6d/ε⌉^d Leaf CellsResearch Paper

Nearest neighbor searching asks for a data structure that stores nnn points S⊂RdS\subset\mathbb R^dS⊂Rd and, given a query point qqq, returns a point of SSS closest to qqq. It underlies classification, vector quantization, data compression, pattern recognition and similarity search in databases. In dimension d≥3d\ge 3d≥3, exact methods either use space growing like …

8 thms4 active usersReviewed
🏆Completed
Operations ResearchProbability·Captain: mikedeng1

Concentration of Measure and Isoperimetric Inequalities in Product Spaces XII: The Euclidean Traveling Salesman Problem — P(|L_N − M| ≥ t) ≤ K e^{−t²/K} for N Uniform Points in the SquareTextbook

The Euclidean traveling salesman problem asks for the shortest closed route through a finite set of points in the plane. Even when the points are placed independently and uniformly in a square, finding an individual shortest route is computationally difficult. A separate probabilistic question is whether the optimal length varies much from one random sample…

7 thms4 active usersReviewed
🏆Completed
CombinatoricsDiscrete GeometryGraph Theory·Captain: mikedeng1

A Combinatorial Theorem in Plane Geometry: Every n-Triangulation Can Be Partitioned into at Most ⌊n/3⌋ FansResearch Paper

In a conversation reported by Chvátal, Victor Klee asked for the smallest number f(n)f(n)f(n) such that every region bounded by a simple closed nnn-gon is dominated by f(n)f(n)f(n) points: every point of the region sees one of them along a segment inside the region. In the picturesque language that gave the problem its name, f(n)f(n)f(n) is the number of guards needed to watch any ar…

7 thms4 active usersReviewed
Discrete GeometryGraph Theory·Captain: hao jia

Uniform Obstacle Bounds for Planar Graphs (OPG-37357)Open Problem

An obstacle representation turns a graph into a visibility system: vertices are points in the plane, and nonedges are blocked by polygonal obstacles. The obstacle number asks for the minimum number of obstacles needed. OPG-37357 records two different questions for planar graphs. The first asks whether one obstacle can ever be insufficient. The second asks…

6 thms4 active usersReviewed
Computational ComplexityOperations ResearchTheoretical Computer Science·Captain: Shuze Chen

Near-Optimal Makespan and Parameterized Hardness for Multi-Robot Motion PlanningResearch Paper

Moving several robots through a shared workspace without collisions is a basic problem of robotics and computational geometry. Deciding whether one arrangement of robots can be transformed into another is PSPACE-hard when the number of robots is part of the input, so attention turns to a small number kkk of robots. Known algorithms for kkk square robots in a…

25 thms3 active usersReviewed
Markov ChainQuantum InformationTheoretical Computer Science·Captain: iris

Improved quantum volume estimation with transducers and amortized quantum walksResearch Paper

Estimating the volume of a convex body is a central problem of computational geometry and of the theory of randomized algorithms. Deterministic algorithms with membership access cannot approximate the volume within a polynomial factor using polynomially many queries (Elekes 1986; Bárány and Füredi 1987), while randomized algorithms based on Markov chain…

47 thms3 active usersReviewed
Machine LearningOperations ResearchProbability+1·Captain: Shuze Chen

Dimension Reduction and Coresets for Min-Sum k-ClusteringResearch Paper

Min-sum kkk-clustering partitions a finite point set XXX into kkk clusters so as to minimise the total distance between points that share a cluster. Unlike kkk-median or kkk-means, it does not charge each point to a center, so it can recover clusters that are coherent but have no good representative point, such as two concentric rings. It is the complement of metric…

15 thms3 active usersReviewed
🏆Completed
Optimization·Captain: mikedeng1

Tight Coreset Bounds for (k,z)(k,z)(k,z)-Clustering in Euclidean and Doubling MetricsResearch Paper

A coreset compresses a clustering dataset into a weighted subset whose cost approximates the original cost for every permitted choice of centers. An optimization algorithm can work on that subset after the input has been read. The number of retained locations therefore matters independently of the time needed to inspect the original data. The question here…

17 thms3 active usersReviewed
Complexity TheoryTheoretical Computer Science·Captain: iris

Hardness of Approximation for Semialgebraic CSPs: Every Geometric Semialgebraic CSP is Approximation ResistantResearch Paper

A constraint satisfaction problem (CSP) is approximation resistant if no polynomial-time algorithm beats a trivial baseline by a constant: on near-satisfiable instances, finding an assignment better than the baseline by any fixed ϵ>0\epsilon>0ϵ>0 is NP-hard. Håstad proved this for 3SAT with the uniformly random assignment as the baseline (Håstad 2001). Later work…

71 thms3 active usersReviewed
Graph TheoryProbabilityTheoretical Computer Science·Captain: iris

Deterministic Approximate Nearest Neighbors in High DimensionsResearch Paper

In the (1+ε)(1+\varepsilon)(1+ε)-approximate nearest-neighbor problem ((1+ε)(1+\varepsilon)(1+ε)-ANN) a set PPP of nnn points of Rd\mathbb R^dRd is preprocessed into a data structure, and each later query q∈Rdq\in\mathbb R^dq∈Rd must be answered by a point x^∈P\hat x\in Px^∈P with ∥q−x^∥2≤(1+ε)min⁡x∈P∥q−x∥2\|q-\hat x\|_2\le(1+\varepsilon)\min_{x\in P}\|q-x\|_2∥q−x^∥2​≤(1+ε)minx∈P​∥q−x∥2​. It is a basic primitive of similarity search, clustering and…

75 thms3 active usersReviewed
Graph TheoryProbabilityTheoretical Computer Science·Captain: iris

Sparse α\alphaα-Navigable Graphs in Euclidean Space via Steiner PointsResearch Paper

Most practical systems for approximate nearest neighbor search in high dimension store the data set P⊂RdP\subset\mathbb R^dP⊂Rd as a directed graph and answer a query qqq by greedy search: starting at some vertex, as long as an out-neighbor of the current vertex is closer to qqq than the current vertex is, move to the out-neighbor closest to qqq; when no such neighbor…

23 thms3 active usersReviewed
ProbabilityTheoretical Computer Science·Captain: iris

Estimating the Volume of a Union of Convex BodiesResearch Paper

Computing the volume of a single convex body in Rn\mathbb R^nRn is #P-hard, yet randomized algorithms approximate it to relative error ε\varepsilonε in polynomial time from a membership oracle (Dyer–Frieze–Kannan 1991; Cousins–Vempala 2018). A union of convex bodies is not convex, so these algorithms do not apply to it directly. Unions arise in Klee's measure…

40 thms3 active usersReviewed
🏆Completed
Algebraic TopologyMachine LearningProbability·Captain: mikedeng1

Persistence-Based Clustering in Riemannian Manifolds: With High Probability the Algorithm Returns as Many Clusters as the Density Has d₂-Prominent PeaksResearch Paper

Mode-seeking clustering groups data points by the peak of an underlying probability density that they "flow up" to. Methods of this kind (mean-shift, graph-based hill climbing) are widely used, but their output depends heavily on noise: a density estimated from finitely many samples has many spurious local maxima, and each of them becomes a cluster. Chazal,…

41 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations ResearchOptimization·Captain: mikedeng1

Economic Lot Sizing: An O(n log n) Algorithm That Runs in Linear Time in the Wagner-Whitin Case 1: The Threshold Rule on Efficient Periods Picks an Optimal Next Production PeriodResearch Paper

Economic lot sizing asks how to meet a known sequence of demands while deciding when to set up production and how much to carry forward. It is a basic deterministic inventory problem: a setup has a fixed cost, production has a per-unit cost, and inventory may be held for later demand. Recomputing every possible next production period in the standard…

8 thms3 active usersReviewed
🏆Completed
CombinatoricsDiscrete GeometryOperations Research·Captain: mikedeng1

A Polynomial Time Algorithm for Counting Integral Points in Polyhedra When the Dimension is Fixed: The Lattice-Point Count of an Integral Simplex Is a Short Signed Sum over Primitive ConesResearch Paper

How many integral points does a polytope contain? The question arises in integer programming, where it measures the size of a feasible set, in combinatorics, where many enumeration problems are lattice-point counts in a polytope (contingency tables, magic squares, flows), in the representation theory of Lie groups, and in the analysis of loop nests in…

16 thms3 active usersReviewed
🏆Completed
Theoretical Computer Science·Captain: wurtle

Generalization of Hinging PlanesResearch Paper

A continuous piecewise linear (CPWL) function is one assembled from finitely many flat pieces glued along flat seams. Every ReLU network computes such a function, and every such function is computed by some ReLU network. Questions about how deep a network must be are therefore questions about the internal structure of CPWL functions.

3 thms3 active users
Operations ResearchOptimizationTheoretical Computer Science·Captain: mikedeng1

Packing Bins in the Euclidean Plane: An Almost-Optimal Approximation for Unsplittable Capacitated Vehicle RoutingResearch Paper

The Capacitated Vehicle Routing Problem (CVRP), introduced by Dantzig and Ramser in 1959, asks for a cheapest set of delivery routes from a depot when each vehicle can carry at most QQQ units. It is a central model of logistics, and most standard benchmark sets use Euclidean distances. In the unsplittable version every client's demand must be delivered by a…

22 thms2 active usersReviewed
PreviousPage 1 of 3Next

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me