**3**

votes

**1**answer

309 views

### The Stock Market Polytope: Explanation?

Ovidiu Racorean.
"Crossing Stocks and the Positive Grassmannian I: The Geometry behind Stock
Market."
(arXiv Abstract link)
Anyone care to offer a summary of what's going on here?
(The ...

**2**

votes

**1**answer

77 views

### Computational complexity of deciding isomorphism of rational polyhedral cones

Let $C,C'$ be rational polyhedral cones in $\mathbb R^n$ both with non-empty interior. Rational means they are generated by vectors with rational entries. One says that $C,C'$ are isomorphic if there ...

**1**

vote

**1**answer

325 views

### Study of convex polytopes via commutative algebra

Let $P \subset \mathbb{R}^d$ be any convex polytope with integral vertices, and let $M$ be the additive submonoid of $\mathbb{R}^{d+1}$ which is generated by $\{ (v,1) : v \in P \cap \mathbb{Z}^d \}$. ...

**1**

vote

**0**answers

27 views

### Euclidean embedding of a graph based on 1-ring neighborhood distances only

Consider a graph $(V,E)$, $\vert V \vert = n$ and weights $\{l_{ij}\}$, where $l_{ij}>0$ iff there is an edge connecting vertices $v_i$ and $v_j$. Distances beyond the 1-ring neighborhood are not ...

**41**

votes

**2**answers

936 views

### How many unit cylinders can touch a unit ball?

What is the maximum number $k$ of unit-radius cylinders with mutually disjoint interiors that can touch a unit ball?
By a cylinder I mean a set congruent to the Cartesian product of a line and a ...

**8**

votes

**3**answers

298 views

### Conjecture on NP-completeness of tesselation of Wang Tile up to finite size

Motivated by these following questions on tessellation:
coloring in lattice
Reference for Wang Tile
Computational approach deciding whether a set of Wang Tile could tile the space up to some size
...

**2**

votes

**1**answer

97 views

### Omit each vertex in turn of convex polygon: Iterative limit?

Let $P=P_0$ be a convex polygon of $n$ vertices $v_k$.
Let $P_{i+1}$ be the convex polygon obtained by intersecting the halfplanes
determined by the lines through every other vertex.
Below, $P_0$ is ...

**6**

votes

**2**answers

138 views

### get a point in polygon (maximize the distance from borders)

I have several 2D polygons represented by lists of xy-coordinates of their vertices.
It is needed to get several points inside the polygon so that they lie possibly far from the polygon's borders ...

**6**

votes

**0**answers

142 views

### Linked circles in R3

Two circles in 3-D are linked iff each one passes through the interior of the other.
There are $N$ points in 3-D in general position (no four lie on a plane). Each triple of points defines a unique ...

**14**

votes

**2**answers

449 views

### Spearing rolling hula hoops

Or: Stabbing rolling disks.
Imagine there are $n$ unit-diameter disks rolling between $x=0$ and $x=d$,
reflecting off either end.
The disk centers start at a random location within $[\frac{1}{2}, ...

**5**

votes

**2**answers

171 views

### Genus of Tutte-Coxeter Graph

What is the genus of the Tutte-Coxeter graph -- the incidence graph of the
GQ of order 2? Seems like it should be well known, since nearly every other
parameter for that graph is known, but I can ...

**15**

votes

**2**answers

314 views

### Trapping a convex body by a finite set of points

In $\mathbb{R}^n$, let $K$ be a convex body and $T$ a finite set of points disjoint from the interior of $K$. Say that $T$ traps $K$ if there is no continuous motion of $K$ carrying $K$ arbitrarily ...

**14**

votes

**3**answers

228 views

### Covering a hexagon

For $\epsilon > 0$ sufficiently small, can a regular hexagon with sides of length $1 + \epsilon$ be covered by seven equilateral triangles with sides of length $1$?
Motivation: Conway and Soifer ...

**2**

votes

**1**answer

45 views

### Integer point in a non-empty polytope

I have a high-dimensional, non-empty polytope $Ax\geq b$ sitting inside the cube ($0\leq x_i \leq 1$). Is there any general theory or technique to show that this polytope contains an integer point, ...

**4**

votes

**2**answers

101 views

### The maximal discrete parallelepiped in a convex body

Does the positive constant $c_d$, depending only from dimension, with the following property exist?
Property:
for every convex body $K\subset \mathbb R^d$ there exists parallelepiped $P\subset K$ ...

**14**

votes

**2**answers

710 views

### Randomly walking a leashed dog

Let a human $h(t)$ random walk on $\mathbb{Z}^2$ by taking a unit-length step at every
time step $t$. A dog $d(t)$ on a leash of length $\lambda$ follows $h(t)$, also
taking a unit-length step at ...

**11**

votes

**1**answer

169 views

### Wander distance of self-avoiding walk that backs out of culs-de-sac

Suppose a self-avoiding walk on $\mathbb{Z}^2$, with random steps each one unit long,
backs out of culs-de-sac, but retaining the lattice points on which it stepped
marked as unavailable for future ...

**27**

votes

**1**answer

503 views

### Can the sphere be partitioned into small congruent cells?

On the unit $2$-sphere ${\mathbb S}^2$ furnished with the geodesic distance, a subset homeomorphic to a planar disk is called a cell. A finite family of cells is a tiling if their interiors are ...

**4**

votes

**2**answers

131 views

### Bound on Minimal Length of Vectors in Lattice and its Dual Lattice

Let $\Lambda$ be a lattice in $\mathbb{R}^n$ and $\Lambda^\ast$ its dual lattice. Let $d=\min_{v\in\Lambda} (v,v)$ and $d^\ast =\min_{v\in\Lambda^\ast} (v,v)$ be the minimal squared lengths of vectors ...

**3**

votes

**1**answer

126 views

### Partition All $n$-bit Binaries into $n$ Parts

For what values of $n$, it is possible to partition $\mathbb{Z}_2^n$ into $n$ disjoint parts, say $A_1, ..., A_n$ such that every element in $\mathbb{Z}_2^n$ is at most one-edit away from each part, ...

**3**

votes

**0**answers

361 views

### N-balls covering n-balls

This question is a follow-on question from:
Covering a unit ball with balls half the radius
The questions are these:
Given an arbitrary dimension d, and a unit n-ball in d-dimensional Euclidean ...

**4**

votes

**1**answer

181 views

### Computational approach deciding whether a set of Wang Tile could tile the space up to some size

As an applied person, I'm facing one practical problem deciding whether a set of Wang tile could tile the plane periodically or aperiodically. Although both problems seem undecidable, but I'm on a ...

**43**

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

**8**

votes

**2**answers

360 views

### Finite field Szemeredi-Trotter theorem with unequal number of points and lines

My question concerns the SzemerÃ©di-Trotter theorem in $\mathbb{F}_q^2$. If we have $m$ points and $n$ lines in $\mathbb{F}_q^2$, then by Cauchy-Schwartz the number of point-line incidences is as most ...

**11**

votes

**2**answers

314 views

### The intersection of a circle and a rank 3 subgroup of the plane

Let $A$ be a rank 3 subgroup of the Euclidean plane, i.e. $A = \mathbb{Z} v_1 + \mathbb{Z} v_2 + \mathbb{Z} v_3$, where $v_1, v_2, v_3 \in \mathbb{R}^2$ are three $\mathbb{Q}$-linearly independent ...

**9**

votes

**1**answer

251 views

### Maximum number of Vertices of Hypercube covered by Ball of radius R

Let $R>0$ be given and let $H^n$ be the unit hypercube in $\mathbb{R}^n$. The problem I am facing is to find the maximum number of vertices of $H^n$ which can be covered by a closed $n$-dimensional ...

**5**

votes

**1**answer

382 views

### Interesting behaviour of Brion's formula under a degenerate change of variables

This is, probably, a question for those knowledgeable on the subject of Brion's theorem and its applications.
Lately, I've been dealing with situations of the following sort. Suppose we are given a ...

**19**

votes

**1**answer

249 views

### Hidden points in polygons

Let $h(n)$ be the largest number of mutually invisible points that can be located in a
polygon $P$ of $n$ vertices. Two points $x$ and $y$ are mutually invisible if the segment
$xy$ contains a point ...

**2**

votes

**1**answer

89 views

### Covering a convex body with its smaller homothetic copies

Given a convex body $C\subset R^d$ and a positive real $\lambda$, any set of the form $\lambda C + x = \{ \lambda c + x \mid c\in C \}$ for some $x\in R^d$ is called a homothetic copy of $C$. The ...

**5**

votes

**3**answers

232 views

### How hard is it to determine if a weighted graph can be isometrically embedded in R^3?

Consider a graph $G$ with nonnegative edge weights.
Question: In $\mathbb{R}^3$, how hard is it to assign coordinates to vertices such that the Euclidean length of each edge is equal to its weight?
...

**3**

votes

**2**answers

273 views

### Consecutive Integer Squared Square

Is it possible to construct a squared square out of consecutive integer squares?
Be it 1,2,3,...n or k,k+1,k+2,...n.

**8**

votes

**1**answer

257 views

### Complexity of the union of randomly rotated unit cubes

It is a remarkable fact that the union of congrent cubes
has only at most near-quadratic combinatorial complexity,
$O^*(n^2)$ for $n$ cubes, known to be almost tight.
This contrasts with the union of ...

**1**

vote

**0**answers

51 views

### Finding special vectors generated by a matrix

Let $G\in \Bbb Z^{n\times n}$ be a unimodular matrix.
Are there any efficient algorithms to find the maximum norm of a vector $v$ that satisfies $\langle\Delta(v),v\rangle=0$ over all vectors $v\in ...

**8**

votes

**3**answers

491 views

### On maximal regular polyhedra inscribed in a regular polyhedron

Let T, C, O, D, or I be regular tetrahedron, cube, octahedron, dodecahedron, and icosahedron, respectively. Suppose that the outer polyhedron have edge-length 1.
For example, it's easy to prove that ...

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

**31**

votes

**0**answers

418 views

### Extending a line-arrangement so that the bounded components of its complement are triangles

Given a finite collection of lines $L_1,\dots,L_m$ in ${\bf{R}}^2$, let $R_1,\dots,R_n$ be the connected components of ${\bf{R}}^2 \setminus (L_1 \cup \dots \cup L_m)$, and say that {$L_1,\dots,L_m$} ...

**20**

votes

**3**answers

2k views

### Can a unit square be cut into rectangles that tile a rectangle with irrational sides?

For arbitrary positive integers $m$ and $n$, if we dissect a unit square into an $m\times n$ rectangular grid of $1/m\times 1/n$ rectangles, we can reassemble these $mn$ rectangles into an $n/m\times ...

**12**

votes

**3**answers

600 views

### Are infinite planar graphs still 4-colorable?

Imagine you have a finite number of "sites" $S$ in the positive quadrant
of the integer lattice $\mathbb{Z}^2$,
and from each site $s \in S$, one connects $s$ to every lattice point to which it
has a ...

**36**

votes

**8**answers

3k views

### A sudden smiley? :-)

This is a vague question, and I will no doubt be (properly!) chastised for posing it.
I would like to generate a set $S$ of points in $\mathbb{R}^3$—$|S|$ finite or infinite—which
has the ...

**34**

votes

**3**answers

1k views

### What fraction of the integer lattice can be seen from the origin?

Consider the integer lattice points in the positive quadrant $Q$ of $\mathbb{Z}^2$.
Say that a point $(x,y)$ of $Q$ is visible from the origin if the
segment from $(0,0)$ to $(x,y) \in Q$ passes ...

**3**

votes

**0**answers

80 views

### Lattices achieving best density

Let $\Lambda \subset \mathbb{R}^n$ be an Euclidean lattice with generator matrix $B$. Define the center density $\delta(\Lambda)$ in the usual way as $\delta(\Lambda) = \rho^n/|\det{B}|$, where $\rho$ ...

**3**

votes

**1**answer

141 views

### Simplex with edges of length at least s having smallest circumradius

Is it true that of all $n$-simplices with edge lengths greater than or equal to some parameter $s$, the regular simplex with edge lengths $s$ has the smallest circumradius? It seems obvious, but I ...

**4**

votes

**1**answer

97 views

### Local rigidity of square disk packing

Is the packing of the plane by disks of radius 1/2 centered at the points of ${\bf Z} \times {\bf Z}$ "locally rigid" in the sense that no finite subcollection of the disks admits any joint ...

**13**

votes

**1**answer

180 views

### Smallest regular simplex containing the unit cube in $R^n$

What is the length $e_n$ of the edge of the smallest $n$-dimensional regular simplex $S_n$ containing the $n$-dimensional unit cube $Q_n$?
In particular, is there $n$ such that ...

**3**

votes

**1**answer

204 views

### Geodesic convex hulls in a graph; and their properties

This question asks for an analog of the convex hull in a graph that parallels
(as far as possible) convex sets in Euclidean space.
Let $G$ be a simple, undirected graph, and let $S \subseteq V$ be a ...

**4**

votes

**0**answers

144 views

### Unique Domino Tiling

Question: how does one enumerate all star-convex $2n$-vertex sublattices of the plane that have the unique domino-tiling property?
Definitions:
A subset S of the xy-plane is star-convex if there is ...

**4**

votes

**4**answers

1k views

### Number of spanning trees in a grid

Given a $\sqrt{n}\times\sqrt{n}$ piece of the integer $\mathbb{Z}^2$ grid, define a graph by joining any two of these points at unit distance apart. How many spanning trees does this graph have ...

**6**

votes

**1**answer

358 views

### Higher dimensional Rubik's cube group

Since "cubes" with higher dimension than three exist I think it's natural to ask for higher dimensional Rubik's cubes. These so called hypercubes don't seem to have been described from a group ...

**11**

votes

**1**answer

487 views

### Tiling the square with rectangles of small diagonals

For a given integer $k\ge3$, tile the unit square with $k$ rectangles so that the longest of the rectangles' diagonals be as short as possible. Call such a tiling optimal. The solutions are obvious in ...

**2**

votes

**0**answers

77 views

### n-dimensional Delaunay Triangulation of Lattices

I have several questions concerning the Delaunay triangulation of a high dimensional lattice.
Given an $n$-dimensional lattice $L$ and its Delaunay triangulation (partition of $R^n$ into simplices ...