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
Operations ResearchOptimizationTheoretical Computer Science·Captain: iris

Inapproximability of Euclidean Steiner TreeResearch Paper

The Euclidean Steiner Tree problem asks for a shortest network connecting nnn given points (terminals) in Rd\mathbb R^dRd, where additional Steiner points may be placed anywhere. It goes back to the Fermat–Torricelli problem, and it is NP-hard already in the plane (Garey, Graham and Johnson, 1977). In fixed dimension it admits a polynomial-time approximation…

30 thms2 active usersReviewed
Machine LearningTheoretical Computer Science·Captain: iris

Parallel Hierarchical Agglomerative Clustering in Low DimensionsResearch Paper

Hierarchical agglomerative clustering (HAC) is a greedy bottom-up clustering method available in SciPy, scikit-learn, fastcluster, R, MATLAB and other data science libraries. Its output, a dendrogram, can be cut at any level to obtain clusterings with any number of clusters, so users need not fix the number of clusters in advance. Different linkage functions…

26 thms2 active usersReviewed
Discrete GeometryOperations ResearchTheoretical Computer Science·Captain: iris

Constant Approximation Algorithms for Knapsack and Bin Packing for Convex PolygonsResearch Paper

Geometric knapsack asks which objects of a given family fit together in a limited region. It models cutting and nesting problems, where allowing rotations can improve material use. For axis-aligned rectangles, with or without quarter turns, constant-factor approximations have long been known. Under arbitrary rotations the problem was much less understood:…

46 thms2 active usersReviewed
CombinatoricsGraph TheoryTheoretical Computer Science·Captain: iris

Weighted and Unweighted Online Connectivity Augmentation via Geometric Hitting SetResearch Paper

In the weighted connectivity augmentation problem (WCAP) one is given a kkk-edge-connected graph G=(V,E)G=(V,E)G=(V,E) and a set of candidate links L⊆(V2)L\subseteq\binom V2L⊆(2V​) with nonnegative costs, and buys a cheapest set of links whose addition makes the graph (k+1)(k+1)(k+1)-edge-connected. Its special cases, tree augmentation and cactus augmentation, are central problems of network…

56 thms2 active usersReviewed
Linear algebraMachine Learning·Captain: mikedeng1

Turning Big Data into Tiny Data: Constant-Size Coresets for k-Means, PCA, and Projective Clustering I: The Rank-m SVD Truncation Plus Its Residual Preserves the Cost of Every j-Dimensional ShapeResearch Paper

Large data sets make clustering and subspace fitting expensive because a candidate solution must be evaluated against every input point. A dimensionality reduction replaces the data by a lower-rank matrix whose costs approximate those of the original input for an entire class of candidate solutions. Feldman, Schmidt, and Sohler study reductions that retain…

11 thms2 active usersReviewed
Discrete Geometry·Captain: mikedeng1

Polylogarithmic Approximation for Packing Convex PolyhedraResearch Paper

Three-dimensional packing occurs when a collection of parts must share a container and its volume determines a cost. In additive manufacturing, the orientation of a part can be chosen before its position because orientation affects surface quality, support requirements, and production time. A mathematical version therefore keeps each shape's orientation…

15 thms1 active userReviewed
OptimizationProbabilityTheoretical Computer Science·Captain: Shuze Chen

Adversarially Robust Streaming Algorithms for (k,z)(k, z)(k,z)-ClusteringResearch Paper

kkk-Median and kkk-Means are among the most studied clustering problems. Both are cases of (k,z)(k,z)(k,z)-clustering in Rd\mathbb R^dRd: given a dataset PPP, find at most kkk centers that minimise the sum of the zzz-th powers of the Euclidean distances from the points to their nearest center. In the dynamic geometric stream model of Indyk (2004), the data arrive as insertions and…

11 thms1 active userReviewed
Machine LearningOperations ResearchTheoretical Computer Science·Captain: Shuze Chen

The Price of Capacities for Clustering CoresetsResearch Paper

A coreset compresses a large data set into a small weighted set on which a family of clustering queries can be evaluated with relative error ε\varepsilonε. Coresets for Euclidean (k,z)(k,z)(k,z)-clustering (kkk-median for z=1z=1z=1, kkk-means for z=2z=2z=2) are a standard tool for streaming, distributed and approximation algorithms, and their optimal size has been the subject of a…

22 thms1 active userReviewed
CombinatoricsGraph TheoryTheoretical Computer Science·Captain: iris

Parameterized Tractability of Euclidean k-Steiner TreeResearch Paper

A Steiner tree connects a set of terminals by a network of minimum total length, possibly through auxiliary Steiner points. In the discrete Euclidean variant the Steiner points must be chosen from a finite candidate set given in the input, and in the kkk-Steiner variant at most kkk of them may be used, while the number of terminals is unrestricted. Exact…

32 thms1 active userReviewed
Markov ChainProbabilityTheoretical Computer Science·Captain: Shuze Chen

An FPRAS for Mixed VolumesResearch Paper

For compact convex sets K1,…,Km⊆RnK_1,\dots,K_m\subseteq\mathbb{R}^nK1​,…,Km​⊆Rn, Minkowski showed that the volume of a weighted Minkowski sum is a homogeneous polynomial of degree nnn in the weights,

27 thms1 active userReviewed
Discrete GeometryGraph Theory·Captain: iris

The Stretch Factor of Planar Delaunay Triangulations Is Nearly DeterminedResearch Paper

A Delaunay triangulation of a finite point set S⊂R2S\subset\mathbb R^2S⊂R2 is a triangulation in which the open circumdisk of every triangle contains no point of SSS. Its stretch factor is the worst ratio dD(u,v)/∥u−v∥d_D(u,v)/\|u-v\|dD​(u,v)/∥u−v∥ over pairs u≠vu\ne vu=v of SSS, where dD(u,v)d_D(u,v)dD​(u,v) is the length of a shortest path from uuu to vvv along the edges of DDD. A uniform bound ttt on this ratio makes…

32 thms1 active userReviewed
ProbabilityTheoretical Computer Science·Captain: mikedeng1

Optimal Zonotope Containment via Adaptive Gaussian SamplingResearch Paper

A zonotope represents every sum of a finite collection of vectors when each vector's coefficient may vary independently between minus one and one. Such representations occur in reachability analysis and verification, where a geometric set describes a family of possible states. A basic question is whether all of those states belong to a prescribed outer…

13 thms1 active userReviewed
Machine LearningNumerical AnalysisTheoretical Computer Science·Captain: iris

Softmax Attention with Any Temperature in Fixed Dimension: Matching the Best Known Maximum-Inner-Product BoundsResearch Paper

Softmax attention is the basic operation of Transformers (Vaswani et al., 2017). Direct evaluation compares every query with every key, so a context of length nnn costs n2n^2n2 exponentials even when the dimension is fixed. A question for theory is whether this quadratic cost is necessary, and how attention relates to the classical batch maximum inner product prob…

30 thms1 active userReviewed
Linear algebraMachine Learning·Captain: mikedeng1

Turning Big Data into Tiny Data: Constant-Size Coresets for k-Means, PCA, and Projective Clustering II: An SVD Coreset of at Most 2(j + ⌈j/ε⌉ − 1) Weighted Points for Affine j-SubspacesResearch Paper

Principal component analysis (PCA) asks for the jjj-dimensional affine subspace that best fits a cloud of nnn points in Rd\mathbb R^dRd in the least-squares sense. When nnn is very large, or the points arrive as a stream or are spread over many machines, one wants to replace the data by a small summary on which the cost of every candidate subspace can still be…

7 thms1 active userReviewed
PreviousPage 2 of 2Next

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