**9**

votes

**2**answers

274 views

### The area of the intersection of convex sets with prescribed pairwise intersections

Consider two numbers $a>b>0$. Let $A_1,A_2,A_3$ be three convex sets in ${\mathbb R}^2$ such that $\mu(A_i)=a$, $\mu(A_i\cap A_j)=b$ ($\mu$ is the usual measure on ${\mathbb R}^2$). What is the ...

**11**

votes

**1**answer

187 views

### Metric conditions on configurations of points with only finitely many solutions

There is an old puzzle, which I believe I learned from Nob Yoshigahara, that asks for all configurations of four (distinct) points in the plane such that the six pairwise distances assume only two ...

**7**

votes

**3**answers

487 views

### Small 4-chromatic coin graphs

A coin graph is a graph that can be represented by a set of disjoint, except possibly touching, unit disks in the plane (i.e. the disks are the vertices and the edges correspond to the pairs that ...

**10**

votes

**0**answers

238 views

### Update to Shephard's “Twenty Problems on Convex Polyhedra”

Forty-three years ago, Geoffrey Shephard published an influential list of open problems
on convex polyhedra.
Progress has been made on several of his problems, and perhaps some have been completely ...

**7**

votes

**1**answer

729 views

### Primes that are the sum of three squares

This is in some sense an extension of the earlier MO question, "Gaussian prime spirals."
Gaussian primes in the complex plane, $a+b i$, require $a^2 +b^2$ prime off the axes.
The generalization to ...

**57**

votes

**5**answers

3k views

### Gaussian prime spirals

Imagine a particle in the complex plane, starting at $c_0$, a Gaussian integer,
moving initially $\pm$ in the horizontal
or vertical directions. When it hits a Gaussian prime, it turns left ...

**3**

votes

**2**answers

189 views

### Form a $\mathbb{Z}^d$ lattice cycle from given lengths

Suppose you are given a list of integer lengths,
e.g.,
$(5,3,2,2,1,1,2,1,1)$.
The task is to decide if they can form a closed cycle
in $\mathbb{Z}^d$ by connecting segments of those
lengths in order, ...

**17**

votes

**2**answers

961 views

### Erdős-Szekeres for first differences

The classical Erdős-Szekeres theorem says that any sequence of $n^2+1$
real numbers contains a monotonic $(n+1)$-term subsequence. Suppose, however,
that we want to find a subsequence which is not ...

**17**

votes

**3**answers

539 views

### Sperner Lemma Applications

I was always fascinated with this result. Sperner's lemma is a combinatorial result which can prove some pretty strong facts, as Brouwer fixed point theorem. I know at least another application of ...

**6**

votes

**0**answers

663 views

### Interpolating points with minimum curvature constraint

I have $n$ points $p_i$ strictly interior to a rectangle $R$,
and I would like to connect them with a curve $C$ whose curvature is as low as possible.
Let $\kappa_\max(C)$ be the sharpest (largest ...

**4**

votes

**2**answers

335 views

### Conformal structure does not see conical singularities

the conformal structure does not see the conical singularities of a polyhedral surface.
This is a quote from the Preface of Quantum Triangulations (eds.: Carfora, Marzuoli).
The sentiment is ...

**3**

votes

**1**answer

410 views

### Tverberg partitions with less than (r-1)(d+1)+1 points

The Tverberg Theorem states the following: Let $x_1,x_2,\dots, x_m$ be points in $R^d$ with $m \ge (r-1)(d+1)+1$. Then there is a partition $S_1,S_2,\dots, S_r$ of $\{1,2,\dots,m\}$ such that $\cap ...

**2**

votes

**0**answers

214 views

### Erdős-Szekeres empty pseudoconvex $k$-gons

I am wondering if the
Erdős-Szekeres
empty convex $k$-gon question has a different answer if
convexity is replaced by a pseudoline-version of convexity.
The empty convex $k$-gon question
is a variant ...

**10**

votes

**1**answer

444 views

### Polygons uniquely inducing arrangements

A beautiful, relatively recent result is that,
Every simple arrangement $\cal{A}$ of $n$ lines in the plane is induced by a simple $n$-gon $P$.
In a simple arrangement, every pair of lines ...

**7**

votes

**1**answer

264 views

### Does the Hirsch conjecture hold for $n < 2d$?

The Hirsch conjecture asserts that the graph (i.e. $1$-skeleton) of a $d$-dimensional convex polytope with $n$ facets has diameter at most $n - d$.
After being open for decades, Francisco Santos has ...

**7**

votes

**3**answers

242 views

### Expected minimum face angle of random convex polyhedron in $\mathbb{R}^3$

Let $P_n$ be a "random convex polyhedron" in $\mathbb{R}^3$ of $n$ vertices, where "random" could follow any one
of a number of models:
(1) the convex hull of $n$ points randomly and uniformly ...

**11**

votes

**1**answer

465 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 polygon of $n$ ...

**26**

votes

**2**answers

833 views

### Bodies of constant width?

In two-dimensional case one can generalize figures of constant width as figures which can rotate in a covex polygon.
Here is one example which can be used to drill triangular holes:
I would like to ...

**4**

votes

**4**answers

801 views

### Delaunay triangulations and convex hulls

This is a reference request.
I have the impression that those who work in computational geometry are accustomed to the following. You have some locally finite set of sites in $\mathbb{R}^n$ and you ...

**24**

votes

**2**answers

637 views

### chromatic number of the hyperbolic plane

A notorious problem in combinatorics is the following:
If we color $\mathbb{R}^2$ so that no pair of points at unit distance get the same color, what is the fewest number of colors required?
This ...

**3**

votes

**0**answers

231 views

### Coloring $\mathbb{Z}^k$ and a fixed point theorem

This is potentially another approach to this question. I put it as an update there, but perhaps it would be better to post it separately. If we color $\mathbb{Z}^k$ with the $\ell_\infty$ metric in ...

**6**

votes

**3**answers

243 views

### Minimum separating subdivision in Plane

Hi
I was thinking about the following problem:
Given a planar Graph embedded in the plane and a set of points $P$ contained in the faces (no face contains more than one point) I want to determine ...

**1**

vote

**1**answer

231 views

### Characteristics of locally triangle-free graph

Hi
I am given a triangulation $T $ of a set of points $S $ in the plane and a disk $D$ which doesn't contain any triangle. If I now look at the subgraph $G(V,E)$ of $T $ whose vertices are the points ...

**9**

votes

**1**answer

876 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

760 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

339 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

757 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

134 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

595 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

936 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

694 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

231 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

568 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

1k 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

362 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

136 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

130 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

737 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

988 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

455 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

259 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

810 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

630 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

315 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

263 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

563 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

412 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

291 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

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