**2**

votes

**0**answers

41 views

### lower bound for sum of (squared) distances under a minimum distance restriction

I am trying to solve a packing problem in discrete geometry and it would be useful to know the answer to the following problem.
Let $A_1$, $A_2$,..., $A_n$ be $n$ points in the Euclidean plane ...

**0**

votes

**0**answers

31 views

### Experimental Investigations on the Statistics of Infinite, Discrete, Evenly Distributed Pointsets in the Euclidean Plane

I am trying to estimate the distribution of certain planar polygons in the Euclidean plane; to accomplish that, I generate finite set of points, that are evenly distributed in w.l.o.g. the ...

**3**

votes

**2**answers

102 views

### Unit-Distance Polyhedra

What polyhedra are known to have two vertices adjacent if and only if they are of distance $d$ apart, for fixed $d$? For example, regular Platonic solids satisfy this condition, so I am looking for ...

**14**

votes

**1**answer

340 views

### Banach-Mazur distance between the cube and the octahedron

The Banach-Mazur distance $d(X, Y)$ between two normed spaces $X, Y$ of the same dimension is defined as $d(X, Y) = \log\inf \|T\| \cdot \|T^{-1}\|$, where the $T:X \to Y$ is a linear and invertible ...

**12**

votes

**2**answers

509 views

### Lattice n-gons with ordered side lengths 1,2,3,…,n

Consider the octagon in the Cartesian plane with vertices at (0,0), (1,0), (1,2), (4,2), (4,6), (7,2), (7,8), and (0,8).
Are there other (infinitely many) polygons, such as this, lying entirely in ...

**3**

votes

**0**answers

50 views

### Efficient CW structures on squarefree semi-algebraic set

General Setup
Given a collection of $k$ polynomials (with real coefficients) in $n$ real variables, say $f_i(x_1,\ldots,x_n)$, let $V \subset \mathbb{R}^n$ correspond to those $x$-values for which ...

**5**

votes

**1**answer

119 views

### Decidability of convex rearrangements of polygons

Triggered by the MO question,
"How many convex shapes can be made with the pieces of the Stomachion?," I would like to pose this question:
Q. Given $n$ polygons in a set $S$, say each with integer ...

**7**

votes

**1**answer

66 views

### minimum number of bases of a matroid, that comes from a convex polytope

Given a d-dimensional polytope P with n points, then what is the minimum number of simplices that are spanned by vertices of P? This question led my research to matroids and so my question is: what is ...

**3**

votes

**0**answers

106 views

### Zeros of Hilbert series of affine toric varieties

Consider a convex rational polyhedral cone $C\subset\mathbb R^m$ with vertex at the origin. Let $X$ be the corresponding affine toric variety, i.e. $\mathbb C[X]=\mathbb C[\mathbb Z^m\cap C^\circ]$. ...

**4**

votes

**2**answers

129 views

### Classification of symmetries of tilings in surfaces?

Is there a general study of the symmetries of tilings on surfaces?
Conway, Goodman-Strauss & Burgiel classified them on $\mathbb S^2, \mathbb R^2$ and $\mathbb H^2$, with their 'Magic Theorem'. ...

**2**

votes

**0**answers

53 views

### What do you call the collection of all sets shattered by $F$?

The proof of Pajor's lemma uses the collection of all sets $S\subseteq X$ shattered by some $F\subseteq 2^X$. Is there a standard term for the former object? I've been privately referring to it as the ...

**0**

votes

**0**answers

34 views

### Minimal subset of an $n$-dimensional grid intersecting every ($n$-dim) arithmetic progression of length $k$

Let $$A=\{1,2,...,l\}^n \subset \mathbb{R}^n$$ for some positive integers $l$ and $n$, and $B \subset A$ be a set such that $|B| \ll l^n$. I am interested in determining how small must $B$ be in ...

**14**

votes

**0**answers

151 views

### Precise estimate for probability an $n$-point set has diameter smaller than $1$

This question was inspired by an earlier question that I answered but would like a more precise bound for.
Consider random points $x_1, \dots, x_n$ in the unit ball in $\mathbb R^d$, uniformly and ...

**2**

votes

**0**answers

82 views

### Balanced partitions of vector sets

We are interested in the following
Lemma. Let $V\subset [0,1]^n\subset\mathbb R^n$ be a set of $n$-dimensional vectors. Then for each $r\le |V|$ there exists a partition $$V=V_1\cup V_2\cup\dots \cup ...

**1**

vote

**1**answer

72 views

### Testing whether two vertices are neighbours

I face the following problem: I am given a high-dimensional, convex, bounded polyhedron in both vertex description: $X = \mathrm{conv} \, \{ v_1, \ldots, v_K \}$ and halfspace description: $X = \{ x ...

**5**

votes

**2**answers

142 views

### Minimum length of a convex lattice polygon containing k lattice points?

Let $f(k)$ denote the minimum length of a convex lattice polygon containing exactly $k$ lattice points (including lattice points on the boundary).
It is not too hard to show that $k = \frac{1}{4\pi} ...

**12**

votes

**0**answers

102 views

### Rational inscribed realization of the regular dodecahedron

While it is clear that the regular dodecahedron $D$ cannot be realized with all integer coordinates, it is easy to find a polytope, which is combinatorially equivalent (face lattice isomorphic) to $D$ ...

**9**

votes

**0**answers

150 views

### Determining convexity of a polygon from its Fourier coefficients

Consider an $n$-sided polygonal curve in the plane, represented by an ordered set of points $(x_0, x_1, \ldots, x_{n-1})$; line segments connect consecutive points and also $x_{n-1}$ to $x_0$. It is ...

**2**

votes

**1**answer

54 views

### Constructing a polygon of $n$ facets from a set of positive values representing the length of the facets [closed]

The input of my problem is a set of positive values $a=\{a_1,...,a_n\}$ where $n\geq 3$.
I want to construct an $n$-gon where the lengths of the $n$ facets are the values $a_i$ for $i=1,...,n$.
My ...

**12**

votes

**1**answer

240 views

### Covering the unit sphere by open hemispheres

Suppose $H_1,\ldots,H_{2n}$ are open hemispheres which cover $S^{n-1}$ with the property that removing any one of them leaves $S^{n-1}$ uncovered. Is it necessarily the case that the hemispheres can ...

**8**

votes

**1**answer

237 views

### Integer sets with forbidden differences

Given a finite set $S$ of positive integers, and a positive integer $n$, let $F(n,S)$ be the largest possible cardinality of a subset of {$1,2,\dots,n$} no two of whose elements differ by a number in ...

**1**

vote

**0**answers

24 views

### Homology of the subcomplexes of the “diamond shaped” sphere under 1-norm in $R^n$ as a simplicial complex

The 1-norm on $\mathbb{R}^n$ is defined by $\|v\| = |v_1| + |v_2| + \cdots + |v_n|$ for a vector $v = (v_1, \ldots, v_n) \in \mathbb R^n$.
The unit sphere $S^{n-1}_1$ under the 1-norm is a simplicial ...

**2**

votes

**2**answers

158 views

### Number of ways of tiling a $2 \times n$ rectangle using rectangles with integer sides

How many ways are there of tiling a $2 \times n$ rectangles using rectangular tiles with positive integer side lengths?
I've done some work on this and have found a way of calculating this that's ...

**2**

votes

**0**answers

89 views

### Question on abstract polytopes

Let $(P,\le)$ be an abstract $n$-polytope, with $n\ge 2$. Let $H,H',K$ be $m$-faces, with $0\le m \le n-2$. Is it true that there is a sequence $\{H_0=H,H_1,\ldots,H_{r-1},H_r=H' \} \subseteq P$ so ...

**4**

votes

**0**answers

119 views

### Reference for the notion of polyhedra “degenerations”

Let $P$ be a convex polyhedron and let $P(t)$ be a continuous deformation thereof, such that:
a) $P(0)=P$;
b) for all $t\in[0;1)$ the polyhedron $P(t)$ is strongly combinatorially equivalent to $P$ ...

**0**

votes

**0**answers

32 views

### Non-adjacent Pair of Edges with Minimal Weight Sum

Given an weighted, undirected Graph $G(V,E)$ without loops or parallel edges,
what is the complexity of determining a pair of non-adjacent edges, whose sum of weights is w.l.o.g. minimal?
...

**2**

votes

**1**answer

86 views

### Orthogonal embeddings and edge lengths

I'm interested in orthogonal embeddings of graphs into the 2-dimensional, i.e where vertices are placed at integer co-ordinates and edges are routed along the grid lines and are not allowed to ...

**4**

votes

**0**answers

161 views

### Polynomials representing locally constant functions

Let $K$ be a finite field with $p$ elements.
(a) Let $f\in K\lbrack x\rbrack$ be such that (i) $\deg(f)<p$ and (ii) $f(2x) = f(x)$ for $\geq (1-\epsilon) p$ values of $x$ in $K$. What can we say ...

**2**

votes

**0**answers

87 views

### Sharpening the Loomis-Whitney inequality

The Loomis-Whitney inequality implies that if $A\subset\mathbb Z^n$ is a finite, non-empty set of size $K:=|A|$, then, denoting by $K_1,\dotsc,K_n$ the sizes of the projections of $A$ onto the ...

**0**

votes

**0**answers

46 views

### Question on solving an optimization problem using Variable splitting and ADMM

Tell me if I have found the right approach to the following optimization problem:
$$
min_{x} \frac{1}{2}\left \| Ax-b \right \|_2^2
\\
s.t. \ \ \Phi v=x \ , \ {x^T(1-x)}=0
$$
$A$ and $\Phi$ ...

**3**

votes

**0**answers

79 views

### Is there a Havel-Hakimi for geometric graphs?

Suppose that we are given $n$ points in the plane, with a degree prescribed for each, and the question is whether we can place a geometric graph on them. Is there an efficient algorithm for this?
...

**1**

vote

**0**answers

61 views

### Building an orthogonal embedding for a 4-planar graph

I'm interested in the following paper http://www.computer.org/csdl/trans/tc/1981/02/06312176.pdf
In particular i'm interested in the construction Valiant describes to prove that it is possible to ...

**5**

votes

**5**answers

222 views

### Locked convex polyhedra

Call a set of polyhedra free if it is possible to rigidly move the polyhedra, without any polyhedron intersecting any other, so that their pairwise distances are arbitrary large, and locked otherwise. ...

**5**

votes

**0**answers

53 views

### convex hull of all-ones principal submatrices

For a subset $S$ of $\{1,\ldots,n\}$,
let $\mathbf{1}_S\in\{0,1\}^n$ denote the indicator vector of $S$, with a $1$ on the $i$th coordinate iff $i\in S$. Let $\mathcal{X}$ denote the convex-hull of ...

**2**

votes

**0**answers

53 views

### Characterizing subgroups of R^n with dense factors

It is well known that (additive) subgroups of $\mathbb{R}^n$ are products of discrete subgroups (lattices) by dense subgroups in subspaces. My question is the following: given a generator set of $p$ ...

**3**

votes

**2**answers

119 views

### How many different integer polytopes does square lattice have?

Let $E_n = \{ (i,j) : 0 \leq i,j \leq n-1 \}$. We say that a polytope $P$ is an integer polytope in $E_n$ if all vertices of $P$ belongs to $E_n$.
My question is how many different integer polytopes ...

**15**

votes

**1**answer

565 views

### On convergence of convex bodies

Let $K\subset \mathbb{R}^n$ be a compact convex set of full dimension. Assume that $0\in \partial K$.
Question 1. Is it true that there exists $\varepsilon_0>0$ such that for any ...

**0**

votes

**0**answers

18 views

### min-max problems about sets of points

Many research problems in discrete geometry have the following form:
Given a set $S_n$ of $n$ points, let $Max(S_n)$ be the maximum
[something]. Define:
$$MinMax(n) = \inf_{S_n} Max(S_n)$$ ...

**3**

votes

**0**answers

83 views

### Algorithm for finding the fewest cartesian products to partition a set of points

The question Algorithm for finding the fewest rectangles to cover a set of rectangles was already answered here and a similar question was answered here. Those questions were about regular geometric ...

**2**

votes

**1**answer

93 views

### What is the maximal diameter of a cell in a particular partition of the simplex?

Consider a standard simplex with points $(p_1, \dots, p_n)$, $p_i \ge 0$, and $\sum_i p_i = 1$. Fix a set $\{q_k\}_{k=1}^K$ with $0\leq q_k \leq \infty$ and $i,j\in\{1, \dots, n\}$. Partition it via ...

**13**

votes

**1**answer

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

**10**

votes

**1**answer

228 views

### Optimization of points on a plane

Suppose we have $n$ points on a plane. Let $D$ be the sum of the squares of all the pairwise distances between the points. Let $A$ be the area of the convex hull. What is the minimum possible value of ...

**2**

votes

**1**answer

114 views

### Is it possible to cover all pairs of points at distance at most 1 by constant number of partitions into sets of diameter at most 1?

Let $n$ be a natural number and let $S_n$ be a square $[0,n] \times [0,n]$ in the plane.
We say that a partition $\mathcal{Q} = R_1 \cup \cdots \cup R_t$ of $S_n$ is simple if each of the sets $R_1, ...

**1**

vote

**0**answers

52 views

### VC dimension of infinite cones [closed]

What is the VC dimension of infinite $d$-dimensional cones? ( single cones not double).
I would say $2d + 1$ or $O(d^2)$
Does anybody have any reference or ideas?

**0**

votes

**0**answers

21 views

### Is there a shelling of a (threshold)shifted complex, such that any partial shelling is still (threshold)shifted?

first the relevant definitions:
A complex $\Delta \subset 2^{[n]}$ is a family of subsets of $[n]$ that is closed downwards, i.e. if $A \subset B$ and $B \in \Delta$, then $A \in \Delta$.
A complex ...

**0**

votes

**0**answers

56 views

### What is the minimal number of lines needed to partition a simplex into cells of diameter at most $\epsilon$?

I am studying a problem that requires me to partition the simplex into cells using a particular family of hyperplanes. For concreteness, consider the 2-simplex. I would like to construct lines ...

**7**

votes

**1**answer

201 views

### Unusual isoperimetry and maximizing the measure of unions of translates of a set

Let me state a standard result first. Let a $A\subset \mathbb{R}^d$ be a set of fixed volume. Define $A_t$ to be the set of all points at distance at most $t$ from $A$. Then the volume of $A_t$ is ...

**5**

votes

**2**answers

277 views

### Conjugate transpose and discreteness, for Kleinian groups

Let $G=\langle g_1,\dots g_n\rangle<\mathrm{PSL}_2(\mathbb{C})$ be discrete,
i.e. a finitely generated Kleinian group.
Let $H=\langle g^{\dagger}g\mid g\in G\rangle$,
(the group generated by the ...

**4**

votes

**1**answer

275 views

### Generating function for number of different tessellation checkered rectangle

Let $R_n$ be checkered rectangle sized $n \times 4, n \ge 1$.
Let $a_n$ be number of different $R_n$ tiling with rectangles sized $1 \times 3$.
$\ \ \ $ $\ \ \ $ $\ \ \ $ $\ \ \ $ $\ \ \ $ $\ \ \ ...

**5**

votes

**0**answers

75 views

### What is the maximal convex hull in $\mathbb R^3$ of a tree with fixed total length?

Denote by $\mathcal T_n$ the set of all trees on $n$ nodes. For a tree $T\in\mathcal T_n$, we assign to each edge a non-negative length such that the sum of all lengths is 1. Denote by $v(T)$ the ...