# Questions tagged [discrete-geometry]

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

**2**

votes

**1**answer

73 views

### Algorithm to compute the convex hull of a set of $m$ possibly intersecting convex polygons in the plane

I am trying to find an algorithm to compute the convex hull of a set of $m$ possibly intersecting convex polygons in the plane, with a total of $n$ vertices. Let $h$ denote the number of vertices on ...

**8**

votes

**0**answers

53 views

### Minimizing union of overlapping rectangles

Believe it or not, this has something to do with making triangle-free graphs bipartite...
We have a collection of $k$ axis parallel rectangles with side lengths $(a_i,b_i)$. We want to arrange them (...

**2**

votes

**0**answers

57 views

### Polygons such that $n^2 $ times magnification of a polygon could be covered by exactly $n^2$ original polygon

While studying about covering problems in combinatorics, I got to a simple question:
What polygons can be covered exactly, without any area that is covered twice or area that is outside the covered ...

**3**

votes

**0**answers

92 views

### Fitting $\frac1n\times\frac1{n+1}$ rectangles into the unit square [duplicate]

Consider the set of rectangles $r_n | n \in \Bbb N$ such that rectangle $r_n$ has shape $\frac1n\times\frac1{n+1}$. The total area composed by one copy of each $r_n$ as $n$ ranges from $1$ to ...

**1**

vote

**0**answers

103 views

### Arithmetic that corresponds to combinatorial rectangles and cylinder intersections?

Definable subsets of $\mathbb N$ in the language of Presburger arithmetic are exactly the eventually periodic sets.
In communication complexity the interpretation is more on intersection and union of ...

**4**

votes

**0**answers

53 views

### Large finite subsets of Euclidean space with no isosceles (or approximately isosceles) triangles

Here's a question in combinatorial geometry which feels very much like other questions I'm familiar with but which I can't see how to get a hold of. I'll actually propose two different questions on ...

**1**

vote

**1**answer

75 views

### Is a polytope with vertices on a sphere and all edges of same length already rigid?

Let's say $P\subset\Bbb R^d$ is some convex polytope with the following two properties:
all vertices are on a common sphere.
all edges are of the same length.
I suspect that such a polytope is ...

**26**

votes

**3**answers

659 views

### How many random walk steps until the path self-intersects?

Take a random walk in the plane from the origin,
each step of unit length in a uniformly random direction.
Q. How many steps on average until the path self-intersects?
My simulations suggest ~$8....

**2**

votes

**0**answers

138 views

### How to calculate the positions of the vertices of a deformed cube with different local and global symmetry?

Going over degrees of freedom, it appears that the following construction works, but I have no idea how to calculate exact positions of the vertices, or even a practical approach to approximating them ...

**6**

votes

**2**answers

472 views

### Tiling a square with rectangles whose areas or perimeters are 1, 2, 3, …, N

For which positive integers N does there exist a square that can be completely tiled with N rectangles of integer sides whose areas or perimeters are precisely 1, 2, 3, ..., N?

**17**

votes

**0**answers

192 views

### Can 4-space be partitioned into Klein bottles?

It is known that $\mathbb{R}^3$ can be partitioned into disjoint circles,
or into disjoint unit circles, or into congruent copies of a real-analytic curve
(Is it possible to partition $\mathbb R^3$ ...

**2**

votes

**1**answer

67 views

### A questions concerning Laguerre/Voronoi tessellations

Fix $n>1$ distinguished points $x_1,\ldots, x_n\in \mathbb R^d$, the Voronoi tessellations are the subsets $V_1,\ldots V_n\subset\mathbb R^d$ defined by
$$V_k~~ := ~~ \big\{x\in\mathbb R^d:\quad |...

**0**

votes

**0**answers

38 views

### Periodicity of oscillators in Langton's Ant and powers of $2$

This question based on previous one by me. As Christopher Purcell noticed in his comment, there exist conjecture (which has a lot of counterexamples) that if you take a pair of ants $(n,n+1)$ apart (...

**4**

votes

**0**answers

140 views

### Absolute oscillator in Langton's Ant

We have a simple (or single) block of Langton's Ants colony which includes two ants looking in the same direction. Their positions can be interpreted as knight's walk. The distances between each next ...

**1**

vote

**0**answers

30 views

### Algorithm for Calculating Spheric Convex Hulls of Finite Pointsets

Let the Spheric Convex Hull ($\mathrm{CH}_S$) denote the intersection of all closed spheres that contain a compact $\Sigma\subset\mathbb{R}^n$ and on their boundary at least $n+1$ distinct points of $...