Discrete & Computational Geometry

In 1966, Zalgaller completed the task of determining all edge-to-edge tilings of the sphere by regular spherical polygons, proving that the only possibilities are the Platonic tilings, the Archimedean tilings, the Johnson tilings, the prism and ...

In this paper, we give a spectral approximation result for the Laplacian on submanifolds of Euclidean spaces with singularities by the $ϵ$-neighborhood graph constructed from random points on the submanifold. Our convergence rate for the eigenvalue ...$\left({\left(,,,\right)}^{\mathrm{}\mathrm{}}\right)$

Given a graph $G=(V,E)$ and a set $S\subseteq \left(\begin{array}{c}V\\ 2\end{array}\right)$ of terminal pairs, the minimum multicut problem asks for a minimum edge set $\delta \subseteq E$ such that there is no s-t-path in $G-\delta$ for any $\{s,t\}\in S$. For $|S|=1$ this is the well known s-t-cut problem, but in general the ...$\mathrm{}{\mathrm{}\mathrm{}\mathrm{}\mathrm{}}^{}$$\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}{\mathrm{}\mathrm{}\mathrm{}\mathrm{}}^{}{\mathbb{}}_{\mathrm{}}^{}$

We provide the solution for a fundamental problem of geometric optimization by giving a complete characterization of worst-case optimal disk coverings of rectangles: For any $\lambda \ge 1$, the critical covering area $A^{\ast }(\lambda )$ is the minimum value for which any ...${}^{}$$\mathrm{}$${}_{\mathrm{}}\sqrt{\sqrt{\mathrm{}}\mathrm{}\mathrm{}\mathrm{}}\mathrm{}$${}_{\mathrm{}}$${}^{}$${}^{}\mathrm{}\left(\frac{{}^{\mathrm{}}}{\mathrm{}},,\frac{\mathrm{}}{\mathrm{}},,\frac{\mathrm{}}{\mathrm{}{}^{\mathrm{}}}\right)$${}_{\mathrm{}}$${}^{}{}^{\mathrm{}}\mathrm{}\mathrm{}$$\mathrm{}$$\frac{\mathrm{}}{\mathrm{}}\mathrm{}$

We consider the Voronoi diagram of points in the real plane when the distance between two points a and b is given by $L_p(a-b)$ where $L_p((x,y))={(|x|}^p+{|y|}^p{)}^{1/p}.$ We prove that the Voronoi diagram has a limit as p converges to zero from above or from ...${}_{}$${}_{}$${}_{\mathrm{}}$

We study the behavior at infinity of the farthest and the higher-order Voronoi diagram of n line segments or lines in a d-dimensional Euclidean space. The unbounded parts of these diagrams can be encoded by a Gaussian map on the sphere of ...${\mathbb{}}^{\mathrm{}}$${}^{\mathrm{}}$$\mathrm{}$$\mathrm{}$$\mathrm{}$$\mathrm{}$${}^{\mathrm{}}$$\mathrm{}$$\mathrm{}$$\mathrm{}{}^{\mathrm{}}$

Given positive integers $k\le d$ and a finite field $\mathbb{F}$, a set $S\subset {\mathbb{F}}^d$ is (k, c)-subspace evasive if every k-dimensional affine subspace contains at most c elements of S. By a simple averaging argument, the maximum size of a (k, c)-subspace evasive set is ...${\mathbb{}}^{}$$\mathrm{}\mathbb{}{}^{}$${}^{}{\mathbb{}}^{}$${\mathrm{}}_{}{}^{\frac{}{\mathrm{}}}$${\mathbb{}}^{}$${}_{}$$$

In 1967, Grünbaum conjectured that any d-dimensional polytope with $d+s⩽2d$ vertices has at least $$\begin{array}{c}\hfill {\varphi }_k(d+s,d)=\left(\genfrac{}{}{0pt}{}{d+1}{k+1}\right)+\left(\genfrac{}{}{0pt}{}{d}{k+1}\right)-\left(\genfrac{}{}{0pt}{}{d+1-s}{k+1}\right)\end{array}$$k-faces. This conjecture along with the characterization of equality cases was recently proved by the author (A proof of ...$\mathrm{}$${}_{}$$\mathrm{}$$\mathrm{}\mathrm{}$$\mathrm{}\mathrm{}$

The circumcenter of mass of a simplicial polytope P is defined as follows: triangulate P, assign to each simplex its circumcenter taken with weight equal to the volume of the simplex, and then find the center of mass of the resulting system of ...