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

learn more… | top users | synonyms

58
votes
4answers
7k 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 number? I'm ...
33
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 ...
29
votes
6answers
896 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 ...
29
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 ...
26
votes
4answers
588 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 ...
18
votes
5answers
1k views

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

Pick's theorem says that given a square grid (that is, all points in the plane with integer coordinates) and a polygon without holes and non selt-intersecting whose vertices are grid points, its area ...
12
votes
1answer
465 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
253 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
1answer
437 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
587 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
169 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
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 ...
8
votes
4answers
1k 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 ...
8
votes
1answer
366 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 ...
7
votes
3answers
288 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
130 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
2answers
187 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
36 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
162 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
3answers
268 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 ...
6
votes
1answer
686 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
48 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
60 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
63 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 ...
6
votes
0answers
349 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
135 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
144 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
3answers
242 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 ...
5
votes
1answer
177 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
2answers
144 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 ...
4
votes
3answers
129 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
387 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
275 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
587 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
169 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
322 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
3answers
343 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
128 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
110 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
194 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
192 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 ...
4
votes
0answers
262 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 ...
3
votes
2answers
264 views

Find center of circle of radius $r$ that overlaps exactly $\lfloor \pi r^2 \rceil$ points of the integer grid

Can a circle of a given radius $r$ always be placed (in $\mathbb{R}^2$) such that the number of points with integer coordinates inside the circle is equal to the nearest integer of the circle's area? ...
3
votes
2answers
398 views

Voronoi decomposition implementation in four dimensions?

I'm a software engineer and have been asked to research a Voronoi implementation in four dimensions. I'm not asking for "teh codez" but am interested in approachable tutorials on Voronoi decomposition ...
3
votes
3answers
266 views

Cover a cicular hole with planks

A friend of mine asked me the following question. Whats the minimum number of rectangular planks of unit width (and infinite length) needed to cover a circular hole with diameter $n$? ...
3
votes
1answer
172 views

Tetromino Proof

Prove that an 8 x 8 board cannot be covered by 15 L-tetrominos and one square tetromino (an L-tetromino is a plane figure shown below, constructed from four unit squares arranged in the form of L; a ...
3
votes
1answer
128 views

Lower bound for a set of distances between pairs of points in a plane

There are $N>1$ points in a plane. Consider the set of all distances between pairs of the points. Let $n$ be the number of elements of this set. We know that $$n \leq {N \choose 2}.$$ What is the ...
3
votes
3answers
232 views

Help me name or find the existing name for this geometric concept!

This may have a proper name, if so - let's discuss. If not, let's name it. This is for a web application in C#, so whatever we call it I will start naming as such in my code. I'm taking GPS data as a ...
3
votes
1answer
205 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 ...
3
votes
1answer
136 views

Can all convex polytopes be realized with vertices on surface of convex body?

Each convex polytope $P$ has a combinatorial type, its so-called face lattice. This lattice is just the poset of all faces of $P$ ordered by inclusion. Given one realization of such a combinatorial ...