Discrete geometry includes the study of covering, illumination, packing, convex bodies, convex polytopes, and other metric geometry.

learn more… | top users | synonyms

64
votes
4answers
8k views

Why is a circle in a plane surrounded by 6 other circles?

When you draw a circle in a plane you can perfectly surround it with 6 other circles of the same radius. This works for any radius. What's the significance of 6? Why not some other numbers? I'm ...
34
votes
2answers
2k views

Why can't three unit regular triangles cover a unit square?

A square with edge length $1$ has area $1$. An equilateral triangle with edge length $1$ has area $\sqrt{3}/4 \approx 0.433$. So three such triangles have area $\approx 1.3$, but it requires four ...
31
votes
1answer
1k views

Dividing a square into equal-area rectangles

How many ways are there to tile an $n\times n$ square with exactly $n$ rectangles, each of which has integer sides and area $n$? The sequence $C(n)$ begins 1, 2, 2, 9, 2, 46, 2, 250, 37. Clearly ...
28
votes
6answers
951 views

Prove Existence of a Circle

There are two circles with radius $1$, $c_{A}$ and ${c}_{B}$. They intersect at two points $U$ and $V$. $A$ and $B$ are two regular $n$-gons such that $n > 3$, which are inscribed into $c_{A}$ and ...
26
votes
4answers
654 views

square cake with raisins

Alice bakes a square cake, with $n$ raisins (= points). Bob cuts $p$ square pieces. They are axis-aligned, interior-disjoint, and each piece must contain at least $2$ raisins. Note that a single ...
21
votes
5answers
1k views

Pick's Theorem on a triangular (or hex) grid

Pick's theorem says that given a square grid consisting of all points in the plane with integer coordinates, and a polygon without holes and non selt-intersecting whose vertices are grid points, its ...
18
votes
2answers
228 views

Largest rectangle not touching any rock in a square field

You want to build a rectangular house with a maximal area. You are offered a square field of area 1, on which you plan to build the house. The problem is, there are $n$ rocks scattered in unknown ...
12
votes
1answer
488 views

Circles on the plane such that every line intersects at least one of them but no line intersects more that 100 of them

I have a serious problem with this problem: Is it possible to Draw circles on the plane such that every line intersects at least one of them but no line intersects more that 100 of them !? Any help ...
11
votes
1answer
258 views

Reconstructing a Monthly problem: tree growth on the 2D integer lattice

I'm trying to reconstruct a problem I saw in the Monthly, years ago. Perhaps it'll look familiar to someone. In the integer lattice in the plane, we grow a tree in the following natural way: ...
10
votes
4answers
1k views

Every polygon has an interior diagonal

How does one prove that in every polygon (with at least 4 sides, not necessarily convex), that it is possible to draw a segment from one vertex to another that lies entirely inside the polygon. In ...
10
votes
1answer
440 views

A multi-dimensional Frobenius problem

Inspired by this question. Let $A$ be a subset of ${\mathbb Z}^d$ that generates the whole additive group ${\mathbb Z}^d$, and let $S$ be the additive semigroup generated by $A$. Prove that there ...
10
votes
1answer
651 views

Results related to The Happy Ending Problem

Im giving a small talk for a combinatorics class on the Erdos-Szekeres conjecture regarding the happy ending problem (the paper is focused on recent work regarding the conjecture). I always find that ...
10
votes
2answers
180 views

Partitioning the plane into three sets each intersecting the vertices of every square with side 1?

Q1. Is it possible to partition the plane into three sets such that each of them contains at least one vertex of every square with side 1 ? (I mean all squares of side-length 1, not just those with ...
9
votes
4answers
2k views

Definition of simplex

From Wikipedia: an n-simplex is an n-dimensional polytope which is the convex hull of its n + 1 vertices. I was wondering if the definition is equivalent to say a simplex is synonym of a ...
9
votes
1answer
396 views

“Center-of-Mass” of lattice polygons (generalization of Pick's theorem)

Call a polygon with integer coordinates (in the Euclidean plane) a 'lattice polygon'. Pick's Theorem allows you to efficiently compute the number of lattice points inside this polygon given just its ...
9
votes
1answer
135 views

Infinitely many polygons, no four have a common point

The following question was asked last year at KoMal (May 2015): Do there exist infinitely many (not necessarily convex) 2015-gons in the plane such that every three of them have a common interior ...
8
votes
2answers
69 views

Partitioning $\mathbb{R}^d$ with two convex sets

The problem/puzzle is: Find two convex sets in Euclidean space, $A, B\subseteq\mathbb{R}^d$, such that the number of connected components of $\mathbb{R}^d\setminus (A\cup B)$ is the maximum ...
8
votes
1answer
91 views

Regular polygons constructed inside regular polygons

Let $P$ be a regular $n$-gon, and erect on each edge toward the inside a regular $k$-gon, with edge lengths matching. See the example below for $n=12$ and $k=3,\ldots,11$.       Two ...
7
votes
3answers
322 views

Name this polytope

I was wondering what people call a certain type of shape. It is the shape formed by an orthogonal projection of a hypercube along one of its longest diagonals. In other words, fill in the missing ...
7
votes
1answer
138 views

Helly's Theorem for Biconvex Sets

Helly's Theorem states the following. Suppose that $X_1,X_2,...,X_N$ are convex sets in $\mathbb{R}^d$, such that for any index-set $I$ with $|I| \leq h(d) := d+1$, we have $\bigcap_{i \in I} X_i \neq ...
6
votes
3answers
260 views

Number of point subsets that can be covered by a disk

Given $n$ distinct points in the (real) plane, how many distinct non-empty subsets of these points can be covered by some (closed) disk? I conjecture that if no three points are collinear and no four ...
6
votes
2answers
220 views

Squaring the plane, with consecutive integer squares. And a related arrangement

Q1. I was fiddling around with squaring-the-square type algebraic maths, and came up with a family of arrangements of $n^2$ squares, with sides $1, 2, 3\ldots n^2$ ($n$ odd). Which seems like it would ...
6
votes
2answers
58 views

Which planar angles on an integer lattice are possible?

As shown in this question, you can construct an angle $A$ on 3 integer points on a plane only if $\tan A$ is rational. A natural generalization is to ask which values can planar angles based on 3 ...
6
votes
2answers
257 views

Voronoi Diagrams Proof

I am having a real problem with this proof about voronoi diagrams: Prove that $V(p_i)$ (i.e., the cell of $\operatorname{Vor}(P)$ which corresponds to $p_i$) is unbounded if and only if $p_i$ is on ...
6
votes
2answers
177 views

Regular Pentagon is the Unique Largest Two-Distance Set in the Plane

A two-distance set is a collection of points for which only two distinct distances appear among pairs of points. (That is, the distance between any pair of points is either $x$ or $y$, and these ...
6
votes
1answer
794 views

Intersection of squares/cubes/hypercubes.

One can form a polygon of $4 n$ sides by intersecting $n$ congruent squares (treated as closed sets, i.e., filled squares):          Q1. For which of the ...
6
votes
0answers
135 views

Balanced, center-free set. [closed]

We say that a finite set $\mathcal{S}$ of points in the plane is balanced if, for any two different points $A$ and $B$ in $\mathcal{S}$, there is a point $C$ in $\mathcal{S}$ such that $AC=BC$. We say ...
6
votes
0answers
55 views

Number of circuits that surround the square.

Consider a grid $G$ in the $\mathbb{R}^2$ plane formed by the points $(x,y)$ with integer coordinates i.e. $G=\{(x,y)\in\mathbb{R}^2: x\in\mathbb{Z},\;y\in\mathbb{Z} \}$. For $n>0$ let $B_n$ square ...
6
votes
2answers
99 views

Simplest graph that is not a segment intersection graph

Given a finite collection $S=\{s_1,s_2,\ldots,s_n\}$ of straight-line segments in the plane, their intersection graph $G(S)$ is a graph that contains a vertex $v_i$ for each segment $s_i\in S$, and an ...
6
votes
0answers
424 views

Surface integral for a scalar function defined on a discrete surface

Imagine a polyhedral, discrete surface embedded in $\mathbb{R}^3$. Its faces are all triangles. For each vertex, one can compute the discrete mean and Gaussian curvatures and evaluate the sum of ...
6
votes
0answers
151 views

Covered 10x10 rectangle with L-shapes trominos

We have given L-shaped trominos and a square of size 10x10. Give a nice proof, that 18 L-trominos is the minimal number with which the square can be covered such that it is impossible to insert one ...
6
votes
0answers
153 views

Unit Distance structure of Hoffman Singleton graph

This question has been bugging me since last 3 years. Prove or disprove that Hoffman Singleton is an unit distance graph in $\mathbb R^2$. For those who are new to unit distance graphs, A graph is ...
5
votes
2answers
151 views

Convex polyhedron and its Gauß-curvature

I am trying to prove: A convex polyhedron has positive Gauß-Curvature at every vertex. What we know: Gauß-Curvature at every vertex is given by $K(p) = 2\pi - \sum\limits_{\text{angle } ...
5
votes
3answers
274 views

On coverings of the complex sphere

Here, everything takes place in $\mathbb{C}^d$ for some $d$, and the sphere $\mathcal{S} = \{\mathbf{x}\in\mathbb{C}^d:\|\mathbf{x}\| = 1\}$. Given $\delta > 0$, consider a collection of vectors ...
5
votes
1answer
198 views

The lattice points of a f.g. rational cone form a f.g. monoid.

In their book "Polytopes, Rings, and K-Theory" Bruns and Gubeladze sketch an alternative approach to Gordan's Lemma, which is stated in the headline (f.g. = finitely generated). I don't understand the ...
5
votes
0answers
344 views

Sphere Covering Problem

Is it possible that one can cover a sphere with 19 equal spherical caps of 30 degrees(i.e. angular radius is 30 degrees)? A table of Neil Sloane suggests it is impossible, but I want to know if anyone ...
4
votes
3answers
131 views

What is the name of this property?

If there are 3 intervals, such that any 2 of them intersect, then all 3 of them intersect. For any 4 disks, if any 3 of them have a non empty intersection, then all 4 of them have a common ...
4
votes
1answer
437 views

Which internal angles can a lattice polygon have?

I am wondering if for a lattice polygon an internal angle can take any value? If no which ones not and why? I guess there will be some restrictions due to the discrete nature of the grid but I am ...
4
votes
3answers
323 views

Dissecting an equilateral triangle into equilateral triangles of pairwise different sizes

It is know that a square can be dissected into other square such that no two of the squares have the same size. This is the simplest dissection of that kind: Is it also possible to dissect an ...
4
votes
1answer
698 views

Applications of Morse theory

Background The use of tools from algebraic topology to study simplicial complexes coming from point cloud data has been thoroughly discussed in the papers of Carlsson, Zomorodian, Ghrist, ...
4
votes
1answer
249 views

Is every finite group of isometries a subgroup of a finite reflection group?

Is every finite group of isometries in $d$-dimensional Euclidean space a subgroup of a finite group generated by reflections? By "reflection" I mean reflection in a hyperplane: the isometry fixing a ...
4
votes
3answers
353 views

Average degree of convex hull vertices in a Delaunay triangulation

Let $P \subset \mathbb{R}^2$. The boundary of $DT(P)$, the Delaunay triangulation of the point set $P$, is $conv(P)$. It is also known that the average degree of the vertices of $DT(P)$ is $\lt 6$. ...
4
votes
1answer
220 views

Algebraic proof of Ehrhart's theorem

Let $P \subset \mathbb{R}^d$ be a $d$-dimensional polytope, where all vertices lie on integral coordinates, and let $L(P,n)$ denote the number of integral lattice points contained in the scaled ...
4
votes
3answers
359 views

Euclidean Tilings that are Uniform but not Vertex-Transitive

Basic definitions: a tiling of d-dimensional Euclidean space is a decomposition of that space into polyhedra such that there is no overlap between their interiors, and every point in the space is ...
4
votes
1answer
106 views

One special case of Helly's theorem (for $\text{radius}=1$ circles)

There are $n$ points on the plane. Any $3$ of them can be covered with a radius $1$ circle. Prove that there is a radius $1$ circle that covers all the points. Came to this when tried to prove an easy ...
4
votes
2answers
118 views

Triangulation of hypercubes into simplices

A square can be divided into two triangles. A 3-dimensional cube can be divided into 6 tetrahedrons. Into what number of simplices an n-dimensional hypercube can be divided? (For example, a ...
4
votes
1answer
134 views

Convex hull of $n$-gon and $m$-gon

Suppose you have a convex $n$-gon, and a convex $m$-gon, in the plane. Take the convex hull of the $n+m$ vertices. How many combinatorially distinct hulls can be obtained, where two hulls are ...
4
votes
1answer
138 views

The Erdős-Szekeres problem on points in convex position

The Erdős-Szekeres problem on points in convex position and its proof using Ramsey theorem are well know. The problem goes like this: For every natural number $k$ there exists a number $n(k)$ such ...
4
votes
1answer
295 views

Dirichlet's approximation theorem (simultaneous version): proof via Minkowski's theorem

There is a proof of the Dirichlet's approximation theorem based on Minkowski's theorem. The proof is given on wikipedia (http://en.wikipedia.org/wiki/Dirichlet%27s_approximation_theorem) and it is ...
4
votes
0answers
259 views

Tilings of the plane

There are many possible tilings (or tesselations) of the plane: periodic ones by a - necessarily - finite number of prototiles (e.g. regular tilings) aperiodic ones by a finite number of prototiles ...