Questions tagged [discrete-geometry]

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

Filter by
Sorted by
Tagged with
15 votes
3 answers
1k views

Representation of vectors in $\mathbb{R}^2$ via differences of small vectors.

Is the following fact true? Let $v_1,\ldots, v_k \in \mathbb{R}^2$, $\|v_i\|\leq 1$, be vectors that add up to zero. Does there exist a permutation $\sigma\in S_k$ and vectors $w_1,\ldots, w_k \...
Fiktor's user avatar
  • 1,264
15 votes
2 answers
568 views

Spearing rolling hula hoops

Or: Stabbing rolling disks. Imagine there are $n$ unit-diameter disks rolling between $x=0$ and $x=d$, reflecting off either end. The disk centers start at a random location within $[\frac{1}{2}, d-\...
Joseph O'Rourke's user avatar
15 votes
3 answers
2k views

Combinatorial analogues of curvature

There appear to be many "combinatorial" definitions of curvature as applied to finite simplicial (or regular CW) complexes. For instance, we have the ideas of Cheeger, Muller and Schrader, ...
Vidit Nanda's user avatar
  • 15.4k
15 votes
1 answer
927 views

Are there irregular tilings by L-polyominoes?

I wonder if one can tile the plane with an order-$n$ L-polyomino in a fundamentally irregular manner. I seek help in defining what should constitute "irregular." An L-polyomino of order $n \...
Joseph O'Rourke's user avatar
15 votes
1 answer
1k views

Conjecture: If equal size circular coins are in a convex polygonal frame, with each coin touching exactly one edge, then all the coins can move

Earlier I conjectured that if circular coins of any sizes are in a convex polygonal frame, with each coin touching exactly one edge, then all the coins can move. A counter-example using coins of ...
Dan's user avatar
  • 2,341
15 votes
2 answers
718 views

Tiling survey that updates "Tilings and patterns"?

Can anyone suggest a survey (or surveys) that provides an update to Tilings and patterns by Grunbaum and Shepard? If there's a more recent book, that would be fantastic, but I don't see one. I am ...
Aaron Sterling's user avatar
15 votes
1 answer
301 views

Annihilating random walkers

Suppose there are several walkers moving randomly on $\mathbb{Z}^2$, each taking a $(\pm 1,\pm 1)$ step at each time unit. Whenever two walkers move to the same point, they annihilate one another. ...
Joseph O'Rourke's user avatar
15 votes
1 answer
631 views

Smallest regular simplex containing the unit cube in $R^n$

What is the length $e_n$ of the edge of the smallest $n$-dimensional regular simplex $S_n$ containing the $n$-dimensional unit cube $Q_n$? In particular, is there $n$ such that $e_n<\sqrt{2}(n+1-\...
Jan Kyncl's user avatar
  • 5,981
15 votes
2 answers
767 views

Three squares in a rectangle

One of my colleagues gave me the following problem about 15 years ago: Given three squares inside a 1 by 2 rectangle, with no two squares overlapping, prove that the sum of side lengths is at most 2. (...
udaque's user avatar
  • 153
15 votes
1 answer
371 views

separating points in $\mathbb{R}^d$ by minimal number of planes

Given $n$ points of general position in $\mathbb{R}^d$ (say, $n>d$ and no $d+1$ lie in a hyperplane.) We want to draw $k$ hyperplanes not passing through those points so that they all are in ...
Fedor Petrov's user avatar
15 votes
1 answer
810 views

Ratio of circumscribed/inscribed $(n{-}1)$-gons

As a discrete analog of the MO question, "Löwner-John Ellipsoid: incribed and circumscribed," I've been wondering what might be the maximum ratio of this quantity? Let $P$ be a convex ...
Joseph O'Rourke's user avatar
15 votes
1 answer
2k views

Ping-pong relief map of a given function z=f(x,y)

I have an idea to design a type of Galton's Board to "draw" a relief map of a given two-dimensional function $z=f(x,y)$. A typical Galton's Board drops, say, ping-pong balls through a series of evenly ...
Joseph O'Rourke's user avatar
15 votes
0 answers
474 views

Expanding disks lead to what packing of the plane?

Suppose one sprinkles points uniformly at random on the infinite Euclidean plane, with some density $\rho$ per unit area. View the points as disks of radius zero. Now the radii $r$ of all disks grows ...
Joseph O'Rourke's user avatar
15 votes
0 answers
2k views

Covers of $Z^k$

This is a question related to covers of $Z^\infty$. Is it possible to cover $Z^k$, $k>1$, with the $l_1$-metric by a constant (not depending on $k$) number of collections of subsets $U^0,...,U^c$ ...
14 votes
7 answers
2k views

Finite set of non-collinear points on plane with every point having ≥ 3 equidistant neighbors? [closed]

Does there exist a finite set of points on the Euclidean plane, such that: No 3 points are collinear, and Every one of the points has (at least) three other points in the set at the same distance ...
Joshuav's user avatar
  • 169
14 votes
3 answers
958 views

Can a tangle of arcs interlock?

Can a (finite) collection of disjoint circle arcs in $\mathbb{R}^3$ be interlocked in the sense in that they cannot be separated, i.e. each moved arbitrarily far from one another while remaining ...
Joseph O'Rourke's user avatar
14 votes
4 answers
445 views

Smallest containing simplex

Let $V_n$ be the least real number such that for every convex subset of $\mathbb{R}^n$ with hypervolume $1$ there is a containing simplex with hypervolume $V_n$. What is known about $V_n$? Is there a ...
Vladimir Reshetnikov's user avatar
14 votes
4 answers
1k views

A notion of 2-dimensional tree

Summary: This post has got rather long after the discussion. The main still open Questions are 5 & 6 below. There is work in progress, and I'll post an update at some point. A tree is a connected ...
Agelos's user avatar
  • 1,844
14 votes
2 answers
874 views

Sets of evenly distributed points in the Euclidean plane

Is there a set $P \subset \mathbb{R}^2$ of points in the Euclidean plane whose intersection with every convex subset of $\mathbb{R}^2$ of area $1$ is nonempty but finite? If the answer is yes, can $P$...
Stefan Kohl's user avatar
  • 19.5k
14 votes
2 answers
656 views

How to characterize the regularity of a polygon?

In my research, I've recently started to play with Voronoi tessellations. I currently have a Python code that creates the tessellation and I am trying to color the polygonal regions according to their ...
Caio Tomás's user avatar
14 votes
2 answers
533 views

Are all well behaved "mean" functions on $\mathbb{R}^+$ equivalent?

Given a set $S$, a function $M: S\times S \rightarrow S$ is a mean if it satisfies the properties: $M(a,a)=a\qquad$ (identity) $M(a,b)=M(b,a)\qquad$ (commutativity). and possibly $M(M(a,b),M(a,c))=...
Yaakov Baruch's user avatar
14 votes
1 answer
802 views

The geometry of crinkled aluminum foil

I wonder if the geometry of crinkled aluminum foil has been studied?            The above is a photo of foil I flattened to reuse. It might be ...
Joseph O'Rourke's user avatar
14 votes
1 answer
596 views

Which sets of lattice points have rational generating functions?

Let $P$ be a subset of $\mathbb N^d$ (or of some normal pointed affine semigroup), and suppose that $f:=\sum_{p\in P}\ t^p\in\mathbb Z[[t_1,\ldots,t_d]]$ is a rational function. What can be said ...
Alex Fink's user avatar
  • 582
14 votes
3 answers
1k views

A curious generalization of Helly's theorem

Here is a curious conjectural extension of Helly's theorem. It may follow (if true) from a useful theorem of the kind asked in this MO question: Conjecture: Let ${\cal F}=P_1,P_2,\dots,P_m$ be a ...
Gil Kalai's user avatar
  • 24.2k
14 votes
1 answer
272 views

How many distances are required to calculate all distances among $n$ points in the Euclidean plane?

I want to know all the pairwise distances between points $P_1,P_2,\ldots,P_n$ in the Euclidean plane (or equivalently, I want to reconstruct the set of points up to congruence). Let's say I have an ...
tuna's user avatar
  • 523
14 votes
3 answers
2k views

Optimal wireframe sphere

Suppose you have a length $L$ of metal pipe at your disposal, and you would like to build a wireframe unit-radius sphere, by bending, cutting, and welding the pipe into a connected structure $F$. Your ...
Joseph O'Rourke's user avatar
14 votes
1 answer
912 views

Partitioning the vertices of an n-cube with random hyperplane cuts

An evolutionary biologist asked me a question which boils down, at least in part, to what seems to me an interesting question of combinatorial/probabilistic geometry. It is an old chestnut of a ...
JSE's user avatar
  • 19.1k
14 votes
1 answer
559 views

Sheaves in combinatorics and discrete geometry

I am looking for examples for the application of sheaves, sheaf-like constructions or the (co)homology of sheaves to problems in combinatorics and discrete geometry. For example given a poset $(P,\...
KoopaTroopa's user avatar
14 votes
1 answer
361 views

Exotic line arrangements

I would like to discuss the following problem. Hopefully, you will suggest to me some ideas and bibliography. At first I will provide some basic definitions to set up the notation. Let us consider ...
snaleimath's user avatar
14 votes
1 answer
645 views

Is the Ford disk packing optimal?

Given two unit-diameter disks tangent to a given line and to each other, determining a region bounded by two circular arcs and a line segment, is the Ford disk packing of that region the unique ...
James Propp's user avatar
  • 19.4k
14 votes
0 answers
259 views

Regular $n$-gon with diagonals: bounds on area of largest cell?

Consider a regular $n$-gon of side length $1$ with diagonals. Here is an example with $n=11$ (from geogebra applet). I've been trying to find, in terms of $n$, bounds on the area of the largest cell, ...
Dan's user avatar
  • 2,341
14 votes
0 answers
477 views

Does every convex polyhedron have a combinatorially isomorphic counterpart whose angles between edges are rational multiples of $\pi$?

After reading these very interesting questions, I came up with another one: Does every convex polyhedron have a combinatorially isomorphic counterpart whose angles between all pairs of edges meeting ...
Piotr Shatalin's user avatar
14 votes
0 answers
4k views

Minimum tiling of a rectangle by squares

Given the $n\times m$ rectangle, I want to compute the minimum number of integer-sided squares needed to tile it (possibly of different sizes). Is there an efficient way to calculate this?
didest's user avatar
  • 1,015
13 votes
5 answers
1k views

Packing obtuse vectors in $\mathbb{R}^d$

I came across this attractive theorem: Theorem. In $\mathbb{R}^d$, there can be at most $d+1$ vectors that form an obtuse angle with one another. This was proved1 as a corollary of a lemma about ...
Joseph O'Rourke's user avatar
13 votes
3 answers
1k views

(non-)existence of the aperiodic monotile

The aperiodic monotile problem asks whether there exists a single tile that every tiling of the plane made with it results non-periodic. What is known about this problem? If this tile exists, how can ...
Melquíades Ochoa's user avatar
13 votes
3 answers
819 views

What fraction of n-point sets in the unit ball have diameter smaller than 1?

This question is inspired by a recent talk by Matt Kahle on random geometric complexes. Some simple notation: let $\mathcal{B} \subset \mathbb{R}^d$ be the unit ball in $d$-dimensional Euclidean ...
Vidit Nanda's user avatar
  • 15.4k
13 votes
2 answers
3k views

How many squares can be formed by using n points?

How many squares can be formed by using n points on a 3 dimensional space? Like using 4 points, there is 1 square be formed Using 5 points, still 1 square Using 6 points, 3 squares can be formed
lier wu's user avatar
  • 241
13 votes
2 answers
3k views

How many vertices/edges/faces at most for a convex polyhedron that tiles space?

I wonder if this problem has already been examined before: Consider a convex polyhedron that tiles $\mathbb R^3$. What is the maximum of vertices/edges/faces that such a polyhedron can have? ...
Wolfgang's user avatar
  • 13.2k
13 votes
2 answers
3k views

Subdivision of triangles into congruent triangles

Recently some old notes of mine have gotten me to thinking about the problem of subdividing a triangle into $N$ smaller triangles, all congruent to one another. A little thought shows the following ...
ARupinski's user avatar
  • 5,181
13 votes
1 answer
296 views

Is every finite $d$-dimensional matrix group generated by $d$ elements?

The question is in the title. If $\Gamma\subset\mathrm{GL}(\Bbb R^d)$ is a finite matrix group, can it be generated by (at most) $d$ elements? I suspect that this hope is too naive, but I have no ...
M. Winter's user avatar
  • 12.5k
13 votes
3 answers
414 views

Maximal distance between $2d+1$ points on the $(d-1)$-sphere

If one arranges $2d$ points on the sphere $\mathbf S^{d-1}\subset\Bbb R^d$ at the vertices of the crosspolytope, then one can achieve a minimal spherical distance of $\pi/2$ between any two points, ...
M. Winter's user avatar
  • 12.5k
13 votes
3 answers
658 views

Are there Monohedra with odd numbers of faces?

A monohedron is a convex polyhedron with all faces mutually congruent but with no other symmetry necessarily needed. So obviously, this is a wide class of polyhedra that includes the Platonic solids ...
Nandakumar R's user avatar
  • 5,473
13 votes
2 answers
815 views

Acute triangulation

Assume that $S$ is a finite 2-dimensional simplicial complex equipped with a metric $d$ such that each triangle is isometric to a plane triangle (so $(S,d)$ is a polyhedral space). Is it possible ...
Anton Petrunin's user avatar
13 votes
2 answers
513 views

Double kissing problem

Consider two touching unit balls which will be called central balls. What is the maximum number $k$ of non-overlapping unit balls so that each ball touches as least one of two central balls? An easy ...
Florian Theil's user avatar
13 votes
2 answers
465 views

When does a set of collinearity conditions imply collinearity of all of the points?

Suppose we have a set of $n$ points $\{X_1,X_2,\dots,X_n\}$ in the real plane and $\mathcal{A}$ a family of subsets of $\{1,\dots,n\}$. By a "set of collinearity conditions for $\mathcal{A}$" we mean ...
Mostafa's user avatar
  • 4,454
13 votes
2 answers
1k views

Average degree of contact graph for balls in a box

Imagine you dump congruent, hard, frictionless balls in a box, letting gravity compress the balls into a stable configuration (I believe such configurations are called jammed.) Assume the box ...
Joseph O'Rourke's user avatar
13 votes
1 answer
3k views

What nets fold to polyhedra?

There is a classic (and open) problem asking whether every polyhedron can be unfolded to give a non-overlapping net. The converse problem has been studied asking which polygons can be folded in some ...
Edmund Harriss's user avatar
13 votes
3 answers
1k views

When are Ehrhart functions of compact convex sets polynomials?

Given a lattice $L$ and a subset $P\subset \mathbb R^d$, we define for each positive integer $t$ $$f_P(L,t)=|(tP\cap L)|$$ the number of lattice points in $tP$. Let's say $P$ is nice if $f_P(L,t)$ is ...
Gjergji Zaimi's user avatar
13 votes
3 answers
357 views

Intersecting cylinders around a sphere

Intersecting $n$ unit-radius cylinders, each with axis through the origin, produces a shape circumscribed about a unit-radius sphere:     My question is: For each $n$, which arrangement of cylinders ...
Joseph O'Rourke's user avatar
13 votes
2 answers
859 views

Discrete Morse function from smooth one

Suppose I have a smooth manifold $M$ and a smooth Morse function $f$ on $M$. Is there a standard way to replace $M$ with a cell complex and $f$ with a discrete Morse function such the resulting ...
Niles's user avatar
  • 599

1
3 4
5
6 7
37