# Tagged Questions

**6**

votes

**2**answers

234 views

### Counting valid coordinates

We are given a matrix $D = (d(i,j))_{1 \leq i,j \leq n}$ such that $d(x,z) \leq d(x,y) + d(y,z)$ for each $1 \leq x,y,z \leq n$. It is also known that $d(x,y) \in \mathbb{N}$ (In this question $0 \in ...

**6**

votes

**2**answers

326 views

### Are angles between points enough to decide the realizability?

Let n points in the plane be given whose coordinates we don't know.
Assume, however, that for any triple of the points we know the angle.
Question: Can we decide whether the n points are realizable ...

**7**

votes

**2**answers

386 views

### Visibility interpretation of Riemann zeta zeros on the critical line?

This is a long shot, but ...
The fraction of $\mathbb{Z}^2$ lattice points
visible from the origin
$1/\zeta(2)=6/\pi^2 \approx 61$%.
The fraction of $\mathbb{Z}^3$ lattice points visible
from the ...

**2**

votes

**1**answer

66 views

### Visibility kernels of embedded graphs

Let $G$ be a connected graph embedded in the plane with all edges straight segments.
For $\alpha \in (0,\pi)$, define an $\alpha$-path as a path in $G$ with
all turns at vertices within ...

**3**

votes

**2**answers

215 views

### A problem on chains of squares — can one find an easy combinatorial proof?

Consider the unit square $ S = [0,1] \times [0,1] $. For each $ n \in \mathbb{N} $, we can tessellate $ S $ by the collection
$$
A
= \left\{
\left[ \frac{i}{n},\frac{i + 1}{n} \right] \times
...

**3**

votes

**1**answer

112 views

### Points with pairwise integer distances in the plane

Consider $n>3$ points with pairwise integer distances in the plane! What is the relationship between these $n(n-1)/2$ integers? Do we have a theorem or result about these points? Does there exist a ...

**6**

votes

**1**answer

233 views

### Thinnest 2-fold coverings of the plane by congruent convex shapes

It is an unsolved problem to determine the "thinnest" $2$-fold covering of
the plane by disks.
The $2$-fold coverage problem by disks is to find the minimum number of congruent
(unit-radius) disks ...

**3**

votes

**2**answers

87 views

### Average vertex degree in finite Delaunay triangulations in high dimensions

In $\mathbb{R}^2$ it's known that with a "random" point configuration, the average degree of a vertex in its Delaunay triangulation is 6.
Does anyone know of a similar result in higher dimension? I ...

**8**

votes

**1**answer

346 views

### Coloring of the plane

I would like to know the minimum number k such that the plane R^2 can be coloured with k colors such that no colour contain all the possible distances. In other words, a colouring such that each color ...

**3**

votes

**0**answers

73 views

### A taut string of equilateral triangles

Let $T$ be a unit edge-length equilateral triangle composed of three cylinders each
of (small) radius $r>0$. (By "small" I mean approximately $< 0.1$.)
Think of $T$ as a physical, rigid ...

**2**

votes

**0**answers

176 views

### Dissection of a polygon into convex polygons

Problem: for a fixed integer $m\geqslant 3$ find all $n$ such that no $n$-gon can be dissected into convex $m$-gons.
I would be very grateful for any information on this problem.
Remark 1. There ...

**4**

votes

**2**answers

125 views

### (non-)existence of the aperiodic monotile

The aperiodic monotile problem asks whether there exists a single tile that every tiling made with it results non-periodic. What is known about this problem? If this tile exists, how can it be/not be? ...

**7**

votes

**1**answer

146 views

### How many maximal triangulations of a rectangle?

I posted the following question on MathStackExchange, but I didn't any answer. So please let me post it on MathOverflow.
Let $L_{m,n}\subset\mathbb R^2$ be a rectangle given by $[0,m]×[0,n]$ with ...

**29**

votes

**2**answers

595 views

### what-if.xkcd.com: stabbing (simply connected) regions on the 2-sphere with few geodesics

In the latest what-if Randall Munroe ask for the smallest number of geodesics that intersect all regions of a map. The following shows that five paths of satellites suffice to cover the 50 states of ...

**7**

votes

**2**answers

128 views

### Number of edges in linklessly embeddable graphs

Consider graphs over $n$ nodes.
What is the maximum number of edges of a linklessly embeddable graph?
A more general question is the following. Given $\mu$ what is the maximum number of edges of ...

**22**

votes

**2**answers

617 views

### Random points on the unit sphere

Suppose you have $n$ points picked uniformly at random on the surface of $\mathbb{S}^d,$ and let the volume of the convex hull of these points be $V_{n, d}.$ Clearly, $V_{n, d}$ converges to the ...

**6**

votes

**2**answers

184 views

### Pictures of the von Neumann polytope

Are there any graphic portrayals of von Neumann polytopes in low dimensions?

**9**

votes

**1**answer

358 views

### Groups and pregeometries

Definition.
For an infinite structure $\mathcal{A}$ and $cl : P(dom(\mathcal{A})) \longrightarrow P(dom(\mathcal{A}))$ , we say
that $(\mathcal{A}, cl)$ is a structure carrying an $\omega$-homogeneous ...

**2**

votes

**1**answer

109 views

### Distance from constant width bodies

EDIT As @David has observed, my conjecture was clearly wrong for $\ n:=2.\ $ Let me still give it a chance for $\ n\ge 3$.
I'll call a family $\ F\ $ of bound closed convex subsets of $\ \mathbb ...

**6**

votes

**1**answer

158 views

### Minimizing deep holes in sphere packings

What's the current state of knowledge regarding packings of spheres in $n$-space that minimize the supremum of the sizes of the holes? This notion of tightness is more rigid than asymptotic density. I ...

**5**

votes

**1**answer

132 views

### Ham sandwich theorem for discrete measures - reference request

A discrete version of the ham sandwich theorem states as follows (see for instance "Common Hyperplane Medians for Random Vectors" - Hill):
For every $\mu_1,...,\mu_n$ discrete (i.e., purely atomic) ...

**3**

votes

**1**answer

106 views

### Covering points with a shortest lattice spiral

Let $S$ be a finite set of lattice points in $\mathbb{Z}^2$.
My question is, roughly:
Q. How can a shortest lattice spiral that passes through
every point of $S$ be found?
A lattice spiral (my ...

**9**

votes

**1**answer

253 views

### A random variation on Polya's orchard problem

Polya's orchard problem is as follows:
"How thick must the
trunks of the trees in a regularly spaced circular orchard grow if they are
to block completely the view from the center?"
See, ...

**19**

votes

**5**answers

1k views

### What arrangement of unit cubes minimizes surface area?

For each of these two questions, one can assume that the arrangements are polycubes (for which a definition can be found in the excerpt-image below).
Question A. How does one arrange $n$ unit cubes ...

**3**

votes

**5**answers

282 views

### Approaching convex and discrete geometry from other disciplines

I would like to learn some convex and discrete geometry (number 52 in MSC2010). I thought that it would be interesting to approach it from some other parts of mathematics - either by learning ...

**0**

votes

**0**answers

120 views

### “Open Points” in the 1983 proof of Szemerédi-Trotter theorem

I was reading through the 1983 paper "Extremal Problems in Discrete Geometry" and I was confused about the definition of "open point" appearing in this paper. By this point in the paper, the authors ...

**2**

votes

**2**answers

326 views

### Practical use of estimates for the Gauss Circle Problem

This question is related to this and this ones. The Gauss Circle problem asks for the number $N(r)$ of integer points within a sphere of radius $r$ centered at the origin. It is well known that $N(r) ...

**7**

votes

**1**answer

98 views

### Dropping altitudes to achieve nonobtuse planar triangulations: finite or infinite?

Given a planar triangulation of (say) a convex region,
imagine the following process to convert it to a triangulation with
no obtuse angles:
Pick an arbitrary obtuse angle at vertex $a$ of ...

**1**

vote

**1**answer

154 views

### Is there a “Bipartite” Szemeredi-Trotter theorem?

One version of the Szemeredi-Trotter theorem states the following:
Given a set of $L$ lines in the plane, the number of points incident to at least $k$ lines is bounded above by a constant times $L/k ...

**2**

votes

**2**answers

112 views

### Maximum possible number of similar three-colored triangles

I want to maximize the number of similar triangles with vertices from three fixed sets, one vertex from each set. For example, if you fix two points $X$, $Y$ (i.e. two sets with only one member), then ...

**2**

votes

**1**answer

69 views

### Characterization of the medial axis of a surface

I would like to know if the following "characterization" of the medial axis of a surface is correct, and if so, how to prove it.
Let $S$ be a continuous, piecewise smooth, compact surface embedded in ...

**5**

votes

**2**answers

237 views

### Put P inside Q! polygons/polyhedra

We have two Polygons/Polyhedra P and Q.
Does there exist a polynomial time algorithm to decide if we can put P (using translation and rotation) inside Q or not?
First think about the case of which P ...

**10**

votes

**2**answers

517 views

### Cut and Fold Polyhedron!

I have two convex polyhedra such that their sums of side areas are equal. It is true that I can cut one of them and flatten it on the plane, then fold the flattened polygon to reach the other ...

**5**

votes

**1**answer

219 views

### Small remarkable matroids

Working on phased matroids (a generalization of oriented matroid to the complex case) I've found an interesting formula for computing the inner Tutte group (and, hence, all the Tutte groups) ...

**2**

votes

**0**answers

47 views

### Looking for N-dimensional spheres in the configuration space of the colorful Tverberg problem

Here we use standard notation for Tverberg's theorem: Dimension $d$, number of partition blocks $r$, and $N=(r-1)(d+1)$.
The configuration space of Tverberg's theorem is the simplicial complex ...

**2**

votes

**1**answer

128 views

### Regarding the set up of a geometry of numbers lemma

I have a question related to geometry of numbers, which although seems quite basic, I was rather confused by it so I decided to ask here. Let $\Lambda$ be a lattice in $\mathbb{R}^n$.
Let $R_1, ..., ...

**1**

vote

**0**answers

35 views

### Moment lemma for circular arc polygons

A "moment lemma" originally due to Fejes Tóth (I guess) states that if $P$ is any polygon (in $\mathbb{R}^2$) with $k$ sides, then for any $\mathbf{y}$, we have ...

**1**

vote

**0**answers

39 views

### Generalizing Concepts of Planar Euclidean Geometry to Symmetric TSP-Instances

To me it seems possible, to successfully look at symmetric TSP instances from a geometry-point of view.
Examples are:
the diagonals of the convex hull of a set of points in the euclidean plane; ...

**2**

votes

**1**answer

151 views

### intersection of the unit cube and a hyperplane containing the main diagonal

Let $A$ be a linear $m$-dimensional subspace of $\mathbf{R}^n$ $m < n$, containing the point $(1,1,\ldots,1) \in \mathbf{R}^n$,
and consider the intersection of $A$ and the unit cube $\Delta_n$ ...

**4**

votes

**1**answer

139 views

### The number of facets of a polyhedron under linear transformation

Consider a (not necessarily bounded) convex polyhedron $P\subset \mathbb{R}^n$ which has $k$ facets.
Let $L:\mathbb{R}^n \to \mathbb{R}^m$ be a linear transformation.
Question1: Is there a fixed ...

**5**

votes

**1**answer

496 views

### Linear transformation of a polyhedron

Is there a simple proof that shows:
Linear transformation of a $\mathcal{H}$-polyhedron (i.e. the intersection of
finitely many closed half-spaces) is a $\mathcal{H}$-polyhedron.
Minkowski sum of ...

**0**

votes

**0**answers

71 views

### Toric morphism fiber and kernel dimensions

Given a morphism between two smooth toric varieties $f: X \rightarrow Y$, is the dimension of the kernel of $\mathrm{d}f$ at any point $p \in X$ equal to the dimension of the fiber at $f(p) \in Y$?
...

**12**

votes

**2**answers

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

**8**

votes

**1**answer

435 views

### Polyhedron not circumscribed about a sphere

Let $P$ be a polyhedron whose faces are colored black and white so that there are more black faces and no two black faces are adjacent. Show that $P$ is not circumscribed about a sphere.
My teacher ...

**16**

votes

**1**answer

451 views

### Longest of random worm-like paths in $\mathbb{Z}^2$

Imagine at each lattice point of $\mathbb{Z}^2$ within $[1,3n]^2$,
with coordinates
$\equiv 2 \bmod 3$,
we place, with equal probability, one of these six patterns:
The result ...

**0**

votes

**0**answers

54 views

### Paths on Cartesian products of graphs satisfying linear constraints

Assume integers $d > r > 0$ and a connected graph $G$ with $d$ vertices. Every point on the $r$-fold Cartesian product of $G$ with itself, $G^{\square r}$, is equivalent to a dimension-$d$ ...

**5**

votes

**2**answers

218 views

### Discrete gradient on point clouds

I am interested to know some ways to approximate discrete gradient if you have a function on point clouds in 2D or 3D.
If you have a function defined on a grid, it well known that you can use a ...

**1**

vote

**1**answer

196 views

### Positroids and Totally Nonnegative Complex Grassmanian

Recently I begin working on matroids, in particular to a generalization of oriented matroids to the complex case.
I found on arxiv the following interesting articles:
1)Alexander Postnikov: Total ...

**6**

votes

**1**answer

141 views

### Hiding $k$ disks inside a larger disk

Suppose one has $k$ unit-radius disks, and the goal is to hide them inside
a disk of radius $R \gg k$.
The detection probes are rays along a line.
(Think of the disks as tumor cells, and the rays as ...

**4**

votes

**1**answer

181 views

### Light inside a polyhedron

I have two questions the same as Mostafa's Question:
Visibility of vertices in polyhedra
Suppose $P$ is a closed polyhedron in space (i.e. a union of polygons which is homeomorphic to $S^2$) and $X$ ...