**9**

votes

**1**answer

923 views

### Numbers of intersection points and lines

Hello,
I don't know if this question has already been posted, I have made a little search with keywords and did not found it, sorry if I missed anything.
Is it possible to characterize the set of ...

**17**

votes

**2**answers

779 views

### Placing points on a sphere so that no 3 lie close to the same plane

Motivation
I am working with arbitrary parallelopiped tilings given by projection from a higher dimensional space. The collection of tiles, and some properties of the higher dimensional space are ...

**8**

votes

**2**answers

351 views

### Limit shape for fixed-perimeter lattice polygons

Let $P$ be a simple polygon defined by $n$ unit-length segments
connecting lattice points of $\mathbb{Z}^2$.
I have two operations that preserve the perimeter of $P$.
The first is the "pop" of a ...

**8**

votes

**7**answers

760 views

### 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 ...

**1**

vote

**0**answers

136 views

### When is the conical hull of a finite set of vectors a subset of the space? (and tilings)

Consider a hypercube in n-dimensions, and take some projection down to an m-dimensional subspace. Now take all vertices and m-1 dimensional facets visible from some direction outside the projection. ...

**1**

vote

**1**answer

611 views

### Applications of ham sandwich type results. References? A general principle?

Lately there has been a lot of interest on applications of the ham sandwich theorem and related results. There is a bunch of lecture notes and surveys that touch upon the subject. I dont know of any ...

**10**

votes

**3**answers

943 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 ...

**8**

votes

**1**answer

721 views

### A Desirable Extension of the Nerve Theorem

Backgroud
The Nerve Theorem (see nLab;) asserts that given a finite collection $\cal K$ of compact sets with the property that all non empty intersections of sets in the family are homotopically ...

**-1**

votes

**1**answer

232 views

### Walks that cannot hit the boundary

I've casually proved, as application of some ideas that I am developing, a result that might be of interest in itself. I am completely new in this field and then I would like to ask your help to ...

**4**

votes

**2**answers

592 views

### A Brouwer fixed point theorem on finite sets

I have casually almost (i.e. up to details that shoud work) proved the following discrete version of Brouwer's fixed point theorem. I should have obtained this result as a corollary of quite ...

**10**

votes

**2**answers

2k views

### Weighted area of a Voronoi cell

Let $X = \{ x_1,\dots,x_n\} $ denote a set of $n$ points in the unit square $S = [0,1]\times[0,1]$, and let $w = \{w_1,\dots,w_n\}$ denote a set of weights corresponding to the $n$ points in $X$. ...

**10**

votes

**1**answer

368 views

### Chord arrangement that avoids confining small or large disks

This question is
These two questions are two-dimensional variations on this recent MO question,
"Threading pinholes in the wall of cylinder to pass through an internal coordinate."
Noam Elkies ...

**2**

votes

**0**answers

138 views

### Minimally 6-connected 3D discrete lines that are convex lattice sets

There are several definitions of 3D discrete lines, e.g. http://diwww.epfl.ch/w3lsp/publications/discretegeo/nratddl.html , http://dx.doi.org/10.1007/978-3-642-19867-0_4 . However, I know of none that ...

**3**

votes

**0**answers

131 views

### A fast way to test whether a partial function can be extended to a chirotope of rank 3 ?

Hello,
What is a fast way to test whether a partial function can be extended to a chirotope of rank 3 ? That is: I have a domain
$E = \{1,...,n\}$
and a partial function
$f: E^3 \to \{-1, 0, 1\}$
...

**17**

votes

**3**answers

778 views

### Growing random trees on a lattice $\rightarrow$ Voronoi diagrams

Imagine growing trees from $k$ seeds on a square $n \times n$ region
of $\mathbb{Z}^2$.
At each step, a unit-length edge $e$ between two points of
$\mathbb{Z}^2$ is added.
The edge $e$ is chosen ...

**8**

votes

**3**answers

1k views

### Undecidable problems in geometry

Are there any (many) algorithmically undecidable problems in computational (combinatorial/discrete) geometry?
Update: the Wang tiles answer the question with "any". (I have somewhat overlooked to ...

**4**

votes

**2**answers

473 views

### intersections of real algebraic sets (a bezout-type question)

This question arose when I was trying to understand the Guth-Katz paper on Erdos distance problem, namely, related to Proof of Lemma 2.9 in http://arxiv.org/abs/1011.4105. The proof of that lemma is ...

**3**

votes

**1**answer

267 views

### Enumerating Connected Circle Graphs

Hi
A circle graph is defined as the intersection graph of a set of chords of a circle.
I'm interested in any information which might help to enumerate connected circle graphs.
Thanks
Andy

**2**

votes

**3**answers

817 views

### Draw a Random Line Through a Voronoi Tessellation, What is the Average Number of Voronoi Cell the Line Intersects?

Update: problem reformulation
Following the advice in comments, I now restate my problem using Voronoi
tessellation.
Given a unit hypercube $H_n=\{(x_1,\ldots,x_n)\in \mathbb{R}^n: 0\leq x_i\leq
...

**8**

votes

**3**answers

648 views

### Erdos-Szekeres in high dimensions

All the point sets in this post are in general position. A set of points in $R^d$ is in general position if every $k+1$ points are affinely independent for $k \le d$. If the set contains at least ...

**4**

votes

**1**answer

330 views

### Intersection of boundary facets of a simplicial complex

Suppose you have an equidimensional $n$-dimensional simplicial complex $\Delta \subseteq \mathbb Q^n$; i.e., $\Delta$ is the union of finitely many $n$-simplices that intersect only along proper ...

**6**

votes

**0**answers

254 views

### A question about a blue fan and a red fan and their common refinement

Is the following conjecture true?
Conjecture: Let $M_1$ be a red map and let $M_2$ be a blue map drawn in general position on $S^n$, and let $M$ be their common refinement. There is a vertex $w$ of ...

**6**

votes

**2**answers

264 views

### Small and large pieces of the plane, after countably many generic straight cuttings

A delightful recent problem about disconnecting the plane by straight lines suggested me the following further question, that I can't resist to post.
Let $\mathcal{F} $ be a countable family of ...

**9**

votes

**1**answer

569 views

### 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 ...

**2**

votes

**1**answer

422 views

### Lipschitz constant of Laplace-Beltrami Operator

I already asked this question at stackexchange with no response - so I'll try here.
I'm reading a paper on discrete differential geometry:
Meyer et.al.
They define the Laplace-Beltrami operator at ...

**1**

vote

**2**answers

293 views

### Can a set of tetrahedra glued together by a common vertex be isometrically embedded in R^4?

A collection of triangles with a common vertex $A_1VA_2$, $A_2VA_3$, ... $A_NVA_1$ with specified side lengths can be isometrically embedded in $R^2$ provided the angles around $V$ add up to $2\pi$. ...

**19**

votes

**1**answer

452 views

### Voronoi cell of lattices with the same profile

Definition 1. Given a body $V$ in $\mathbb R^n$,
the function $p_V\colon \mathbb R_+\to \mathbb R_+$
$$p_V(r)=\mathop{\rm vol} [V\cap B_r(0)]$$
will be called profile of $V$.
Definition 2. Define ...

**12**

votes

**1**answer

643 views

### Random polycube shapes

I am wondering if it is hopeless to obtain any firm results
on the following model of a "random polycube shape."
First, a polycube in $\mathbb{R}^3$
is a connected face-to-face gluing of unit cubes.
...

**13**

votes

**1**answer

527 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 ...

**3**

votes

**2**answers

498 views

### Torus in $\mathcal{R}^3$

Hi
I'm interested in packing the 3 space as dense as possible using equally sized tori whose major radius is much bigger than their minor radius in.
Do you have any idea how to attack this problem?
...

**20**

votes

**3**answers

1k views

### Rolling-ball game

The analyses
in two recent MO questions,
"Rolling a random walk on a sphere"
and
"Maneuvering with limited moves on $S^2$,"
suggest a Rolling-Ball Game, as follows.
A unit-radius ball sits on a grid ...

**10**

votes

**2**answers

569 views

### Helly theorem + Nerve

Consider nerve $\mathcal N$ of a finite set of convex sets in $\mathbb R^n$.
Helly theorem says that $\mathcal N$ is completely determined by its $n$-skeleton, say $\mathcal N_n$.
It seems that not ...

**6**

votes

**0**answers

207 views

### balls in arrangements of hyperplanes

The following theorem is from Aronov, Naiman, Pach and Sharir's
An invariant property of balls in arrangements of hyperplanes. I would like to state them and then ask if any related problem/theorem ...

**1**

vote

**1**answer

297 views

### Pointers/Papers on subdivision of planar quadrilateral meshes (PQ-Mesh) in 3D?

I'm interested in the subdivision of planar quadrilateral meshes (PQ-Meshes). Meshes consisting only of planar quadrilaterals, like discrete Voss surfaces and alike. I've been searching the web
for ...

**7**

votes

**0**answers

221 views

### Coloring toroidal polyhedra with convex faces?

Consider a toroidal polyhedron, which is a topological torus, in which all faces are planar, two faces meet in at most an edge, and adjacent faces are not coplanar. The Szilassi polyhedron has 7 ...

**7**

votes

**2**answers

756 views

### The straightest possible path embeddable in a path of polygons

I'm studying a problem involving the sets of discrete curves that can be embedded in a non-trivial polygon, from a source to a target point, as shown below.
Initially my interest was limited to ...

**30**

votes

**1**answer

1k views

### Pach's “Animals”: What if genus $> 0$ ?

Janos Pach asked a deep question 23 years ago (1988) that remains unsolved today:
Can every animal—a topological ball in $\mathbb{R^3}$
composed of unit cubes glued face-to-face—be ...

**20**

votes

**2**answers

881 views

### Forbidden mirror sequences

Let $\cal{M}$ be a finite collection of two-sided mirrors,
each an open unit-length segment in $\mathbb{R^2}$,
and such that the segments when closed are disjoint.
A ray of light that reflects off the ...

**55**

votes

**5**answers

2k views

### Does every polyomino tile R^n for some n?

This is a question posed by Adam Chalcraft. I am posting it here because I think it deserves wider circulation, and because maybe someone already knows the answer.
A polyomino is usually defined to ...

**3**

votes

**1**answer

528 views

### Voronoi polygons of general point patterns forced to honeycomb?

This question comes out of a simple wish for graphical displays of people (say members of the Wikimedia chapter for whom I now work) that will display demographic clustering. Obviously in typical ...

**7**

votes

**3**answers

2k views

### n-dimensional voronoi diagram

Hi, I need to compute the voronoi diagram of a set of points in $R^n$.
I'm quite unschooled on the topic, could someone point me to the right references so that I can
a) understand the theory behind ...

**3**

votes

**1**answer

209 views

### Non-inherited symmetries of shadows of point sets

Sometimes a point set in Euclidean space may have a shadow with an unexpected symmetry. The purpose here is to ask when this happens or when it doesn't happen (in some generality).
This requires a ...

**6**

votes

**0**answers

264 views

### 3-dimensional Cayley graph

I would like to see Cayley graphs drawn in 3-dimensional Euclidean space such that the vertices are represented by points and various shadows display the actions of the generators.
For example, ...

**4**

votes

**1**answer

309 views

### Discrete gradient ascent cycles

I am wondering what can be inferred when a discrete
gradient ascent algorithm gets stuck in a cycle.
Here is the situation.
A function $f(x,y)$ is defined over a range $[0,n]^2$,
and the algorithm ...

**42**

votes

**1**answer

2k views

### two tetrahedra in R^4

It is relatively easy to show (see below) that if we have two equilateral triangles of side 1 in $R^3$,
such that their union has diameter 1, then they must share a vertex.
I wonder whether we have an ...

**1**

vote

**2**answers

596 views

### Is there always a parallelogram cross-section of parallelepiped contained in the smallest box

Let $M$ be a centered parallelepiped, the intersection of $M$ and any plane $P$ that passes through the origin is a parallelogram or hexagon. Each parallelogram or hexagon has a cubic box that is the ...

**8**

votes

**2**answers

651 views

### Are Penrose tilings universal? Do aperiodic universal tilings exist?

Consider a tiling of the plane using tiles of at least two types (e.g, a Penrose tiling such as that shown at the bottom of this question, which tiles the plane with two types of tiles). List the tile ...

**16**

votes

**6**answers

1k views

### Shortest grid-graph paths with random diagonal shortcuts

Suppose you have a network of edges connecting
each integer lattice point
in the 2D square grid $[0,n]^2$
to each of its (at most) four neighbors, {N,S,E,W}.
Within each of the $n^2$ unit cells of ...

**4**

votes

**2**answers

226 views

### Finding the Boundary Faces of the Zonohedron

A zonotope is a linear combination of m vectors with coefficients in [0,1]: $Z = \{ \sum \lambda_i v_i : 0 \leq \lambda _i \leq 1 \}$. The fancy way is to say it's the Minkowski sum of line segments ...

**2**

votes

**1**answer

491 views

### Gluing Polygons

Consider all polygons whose vertices are lattice points and edges are parallel to the axes such that no more than two edges meet at a vertex. For two polygons A and B, define A+B be to the set of ...