MathOverflow Stack Exchange
MathOverflow Stack Exchange

Questions tagged [discrete-geometry]

Finite or discrete collections of geometric objects. Packings, tilings, polyhedra, polytopes, intersection, arrangements, rigidity.

Discrete Geometry includes the study of combinatorial and other aspects of finite or discrete collections of geometric object. It is closely related to combinatorial topology, convex geometry, combinatorial geometry, computational geometry, geometric graph theory and the study of polyhedra and polytopes.

Typical objects of study include circle-, sphere- and other packings, tessellations, arrangements of hyperplanes, configuration spaces, matroids, and lattices.

Methods used to study these objects reach from algebraic geometry, algebraic topology, number theory and graph theory to discrete mathematics, combinatorics and optimization.

1662 questions
65
votes
2 answers

How many cubes cover a bigger cube?

How many $n$-dimensional unit cubes are needed to cover a cube with side lengths $1+\epsilon$ for some $\epsilon>0$? For n=1, the answer is obviously two. For n=2, the drawing below shows that three unit cubes suffice, but it is impossible using…
J.C. Ottem
  • 11,519
22
votes
3 answers

Covering a hexagon

For $\epsilon > 0$ sufficiently small, can a regular hexagon with sides of length $1 + \epsilon$ be covered by seven equilateral triangles with sides of length $1$? Motivation: Conway and Soifer showed that an equilateral triangle with sides $n +…
Matthew Kahle
  • 7,755
12
votes
1 answer

infinite configuration of lines

I was looking at some random problems and questions I liked when I was in high school and I found this one which I still cannot prove. Does there exist a configuration of a countable number of straight lines in the plane such that: 1) no two are…
Manuel Rivera
  • 2,015
11
votes
4 answers

Do there exist two points seeing one another?

Let $n\ge1$ be an integer number. Let $n$ nonoverlapping closed line segments and $n+2$ distinct points which do not belong to those line segments be given in the plane $\mathbb{R}^2$. Can two points among the $n+2$ given points be chosen such…
user64494
  • 3,309
10
votes
7 answers

Omniscient bots gathering on $\mathbb{Z}^2$

There are $N=n^2$ "bots" on distinct integer lattice points in the plane. Each knows the positions $p_i$ of all bots, and each has unlimited (private) memory. Each executes the same algorithm $\cal{A}$: at time $t=0,1,2,\ldots$, bot $i = (t \bmod…
Joseph O'Rourke
  • 149,182
  • 34
  • 342
  • 933
10
votes
3 answers

Maximal packings of the integers

How does one show that for a given packing body $B$ (a finite set of integers) there is a periodic packing of the integers by disjoint translates of $B$ that achieves as its density the supremum of the set of densities achieved by all periodic…
James Propp
  • 19,363
9
votes
3 answers

Balanced circle packing

In the Euclidean plane, given is a collection of $k$ circular disks $D_1,…,D_k$ of radii $r_1,…, r_k$, supplied with weights $w_1,…,w_k$, assuming that each circle’s center of gravity coincides with the circle’s center (in general, the weights are…
Wlodek Kuperberg
  • 7,256
9
votes
0 answers

Neighborly family of coins

Here is a puzzle: Find 5 identical coins. Can you arrange them so that every coin is touching every other coin? The solution is here. The hint is: use the third dimension. My questions are based on this puzzle. Can you prove that six coins can…
Hao Chen
  • 2,541
8
votes
3 answers

monochromatic subset

Suppose we have $n^2$ red points and $n(n-1)$ blue points in the plane in general position. Is it possible to find a subset $S$ of red points such that the convex hull of $S$ does not contain any blue points, where $|S|>n^{\epsilon}$?
Ken
  • 397
  • 1
  • 7
8
votes
2 answers

A question about tilings of the plane

Let C be a compact subset of the Euclidean plane E whose boundary is a Jordan curve J. If C tiles the plane, can J be such that it has a unique tangent line at each point and none of its sub-arcs is a straight line segment with distinct…
Garabed Gulbenkian
  • 6,115
8
votes
2 answers

What's the difference between a PL simplicial sphere and a shellable simplicial sphere?

Shellability of a simplicial sphere tells us that we can build up the complex one facet at a time such that at each step (except the last step) the complex is a PL-ball. At the last step it is of course a PL-sphere. Lickorish showed that there exist…
user80533
  • 81
8
votes
2 answers

Special case of Erdos Distance Problem in a plane

Erdos in his Distinct distance Problem in a plane conjectured that the minimal number of distinct distance determined by $n$ points in a plane be $g(n)$, $$g(n) \sim \frac{cn}{\sqrt{\log n}}$$ But for the special case which asks the minimum number…
r9m
  • 810
  • 6
  • 18
7
votes
1 answer

Largest inscribed triangle with a given vertex

It is known from Blaschke and later Sas that any convex region $P$ with area $1$ admits an inscribed triangle with area at least $\frac{3\sqrt{3}}{4\pi}$. What if we require the triangle to have a given boundary point of P as vertex? The optimal…
Xiaosheng Mu
  • 765
  • 3
  • 12
7
votes
2 answers

Sharpening the Loomis-Whitney inequality

The Loomis-Whitney inequality implies that if $A\subset\mathbb Z^n$ is a finite, non-empty set of size $K:=|A|$, then, denoting by $K_1,\dotsc,K_n$ the sizes of the projections of $A$ onto the coordinate hyperplanes, we have $$ K_1\dotsb K_n\ge…
Seva
  • 22,827
7
votes
1 answer

Seeing the vertices of a polygon with rational angles

Given any convex polygon in the plane, is it always possible to find a point $p$ in its interior such that when we draw the line segments from $p$ to each of its vertices, the angles formed at $p$ are all (not necessarily equal) rational multiples…
Sinai Robins
  • 613
1
2 3