# Tagged Questions

**18**

votes

**2**answers

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

**5**

votes

**2**answers

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

**2**

votes

**1**answer

108 views

### Relation between non-integral polytopes, integrally closed polytopes and polynomial Erhart quasi-polynomials

By lattice points, I will always mean points in $\mathbb{Z}^n$ and all polytopes here are convex rational polytopes.
If $P$ is an integral polytope, the counting function for the number of lattice ...

**2**

votes

**1**answer

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

**14**

votes

**2**answers

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

**4**

votes

**2**answers

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

**11**

votes

**1**answer

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

**4**

votes

**2**answers

164 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

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

**9**

votes

**2**answers

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

**9**

votes

**3**answers

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

**11**

votes

**2**answers

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

**3**

votes

**1**answer

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

**5**

votes

**3**answers

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

**4**

votes

**5**answers

452 views

### Lattice points in dilated polytopes and sumsets

Let $P$ be an integral polytope, that is, the convex hull of some points in $\mathbb{N}^d$.
Let $p_1,\dots,p_m$ be all lattice points in $P$.
Question: What is the condition on $P$ that guarantees ...

**42**

votes

**2**answers

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

**1**

vote

**0**answers

74 views

### Separating unit disks by circles

This is inspired by the recent question about separating unit disks by lines, which I will refer to as the "line case". Replacing "line" by "circle" adds one degree of freedom, and I'm wondering if ...

**7**

votes

**1**answer

242 views

### Separating unit disks by lines

Given $n\ge 2$. For a real $d>2$, consider a constellation $C$ of $2n$ disks of radius $1$ in the plane such that $h(C)$, the minimal distance between any two of their centers, is equal to $d$. Let ...

**1**

vote

**0**answers

102 views

### On 'Very Movable' Geometric Configurations (Configurations with a large degree of freedom)

Let $C$ be an $(n_r, b_k)$ combinatorial configuration that admits a geometric realization in the plane. I'm interested in the maximum number of points/lines $M$ of $C$ we can place in general ...

**33**

votes

**0**answers

517 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$} ...

**22**

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

**3**

votes

**0**answers

1k views

### How many combinations does Android pattern have? [closed]

Rules-
1) At-least 4 and at-max 9 dots must be connected.
2) There can be no jumps
3) Once a dot is crossed, you can jump over it.

**2**

votes

**0**answers

42 views

### How many regions are created by the set of all hyperplanes defined by a set of points?

If we have a set of points X in d-dimensional euclidean space, and we look at the set of all hyperplanes that are defined by any subset Y of X (in the sense of being the unique hyperplane containing ...

**1**

vote

**0**answers

109 views

### intersection points and lines, part two

Two years ago I asked a question about finding couples of integers (p,l) such that one may draw l lines on the euclidean plane, creating exactly p intersection points, and I got very interesting ...

**3**

votes

**0**answers

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

**4**

votes

**1**answer

108 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

**3**answers

725 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

**3**answers

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

**5**

votes

**1**answer

247 views

### Regular lattice polygons

Suppose I want to construct an $N$-gon in the plane whose vertices are integer lattice points, and which is close to a regular $N$-gon (which means, the ratio of longest to the shortest side is within ...

**1**

vote

**0**answers

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

**6**

votes

**1**answer

127 views

### How “accidental” are equalities between parts of Ehrhart quasi-polynomials? When do they persist to Euler-Maclaurin?

Background
What I think of Ehrhart theory (http://en.wikipedia.org/wiki/Ehrhart_polynomial) asserts that if we take a lattice polytope $P$, and count the number of lattice points in the $t$th ...

**0**

votes

**1**answer

172 views

### Expected length of the shortest polygonal chain connecting N random points in the unit square

N points are selected uniformly at random in the unit square. Let L(N) be the expected length of the shortest (possibly self-intersecting) polygonal chain connecting all the points. It can be proved ...

**6**

votes

**0**answers

112 views

### Does every convex polyhedron have a combinatorially isomorphic counterpart whose angles between edges are rational multiples of $\pi$?

After reading these very interesting questions, I came up with another one:
Does every convex polyhedron have a combinatorially isomorphic counterpart whose angles between all pairs of edges meeting ...

**6**

votes

**0**answers

78 views

### Constructing a polyhedron of maximal possible volume from given bounds on areas of its faces

Consider $n$ variables $a_1,...,a_n$ ranging over $\mathbb{R}^+$. Suppose we are given $n$ pairs of positive rational numbers $(p_1,q_1),...,(p_n,q_n)$ where each pair imposes bounds on the ...

**2**

votes

**1**answer

373 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

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

**6**

votes

**1**answer

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

**28**

votes

**1**answer

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

**19**

votes

**1**answer

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

**3**

votes

**1**answer

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

**1**

vote

**2**answers

278 views

### Discrete Laplace operator and its eigenvalues

I wonder is there any geometric interpretation of the eigenvalues of the discrete Laplace operator on graphs? Maybe there is a relationship between the eigenvalues and combinatorial properties of ...

**22**

votes

**3**answers

745 views

### Tetrahedron insphere iteration

I know that iterating the following incircle construction approaches an equilateral triangle in the limit:
Starting with any triangle $T$, one forms $T'$ by connecting ...

**2**

votes

**2**answers

304 views

### Sphere - Symmetry and Triangulation [closed]

The sphere is symmetric with respect to any rotation. However, it loses this property as soon as it is triangulated. Are there sequences of triangulations that possess particular large symmetry groups ...

**0**

votes

**1**answer

56 views

### Optimal radiating $(d{-}1)$-flats within a sphere

Permit me to revisit an earlier unresolved MO question,
"Chord arrangement that avoids confining small or large disks"
with a (very!) specific version, inspired by radiation therapy.
The main idea is ...

**2**

votes

**1**answer

306 views

### Number of 3-tuple partitions of a multiple of three which follow the triangle inequality

Given n=3t, t$\in \mathbb N$; let $\mathbb L_3$ be set of all distinct integer partitions of n having 3 parts; say $\lambda_1,\lambda_2,\lambda_3$ .
If I chose any one partition randomly from ...

**1**

vote

**1**answer

84 views

### Softwares to draw euclidean polyhedral surfaces

Let $S$ be an abstract euclidean polyhedral surface. By this, I mean a orientable compact 2D topological surface obtained by gluing together some (convex) euclidean polygons (arbitrary genus).
...

**5**

votes

**2**answers

500 views

### Is there a 3d equivalent of this picture?

This question arises apropos of an earlier question I asked that was (VERY!!!) helpfully answered by Anton Petrunin:
Fitting a mesh to a density function
The picture below is the image of a regular ...

**5**

votes

**1**answer

350 views

### What are the essential properties of algebraic closure on an arbitrary structure?

Define the "model theoretic" notion of a closure function as follows:
Definition (1): Let $D$ be a non-empty set. A function $cl:P(D)\longrightarrow P(D)$ called a closure function iff it has the ...

**6**

votes

**2**answers

255 views

### Embedding points in 2D based on distance estimates?

Suppose we have a collection of exactly $N$ points (say $N=1000$), with each point belonging to 2-dimensional Euclidean space $\mathbb{R}^2$, but we don't know the coordinates of the points. Suppose ...

**6**

votes

**1**answer

170 views

### Curvature flows for PL closed curves in the plane?

I'm curious to what extent people have studied "curvature flows" on PL closed curves in the plane.
There's a paper by Gage and Hamilton from 1986 that describes the long-term behaviour of smooth ...