**4**

votes

**1**answer

230 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

334 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

486 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

78 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

247 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

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

**35**

votes

**0**answers

558 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

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

49 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

118 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

105 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

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

**14**

votes

**3**answers

796 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

277 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

135 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

184 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

135 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

86 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

508 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

288 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

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

**29**

votes

**1**answer

639 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

324 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

193 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

326 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

819 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

345 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

60 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

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

92 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

548 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

421 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

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

**7**

votes

**1**answer

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

**1**

vote

**0**answers

78 views

### Group actions on polytopes in indefinite integer lattices

Is anything at all known about polytopes in indefinite integer lattices? I'm interested in lattice automorphisms which preserve certain polytopes of "high regularity" (e.g. cones). As a first step, ...

**3**

votes

**0**answers

285 views

### Tiling a rectangle with weighted cells (min-max problem)

I have been struggling with a research problem. The problem can be formalized as follows:
Given a $n\times m$ matrix $A$ containing cells with non-negative integer values, partition it in $J$ ...

**3**

votes

**1**answer

93 views

### Points in general position on a small grid

A point set $P$ is said to be embedded in $\mathbf{Z}^2$ in general position, if no three points lie on a common line. Assume that $|P|=n$, I am interested in the smallest $k \times k$ integer grid in ...

**8**

votes

**1**answer

256 views

### Largest convex hull of a unit length path

What is the largest area possible for the convex hull of a path of unit length lying on a plane? For what paths is that largest area attained?

**2**

votes

**1**answer

104 views

### Estimates on the number of vertices of reflexive polytopes

Suppose $M \cong \mathbb{Z}^n$ is a rank $n$ lattice, with dual lattice $N$. Suppose $\Delta$ is a full dimensional lattice polytope (i.e. convex hull of finite lattice points) in $M$. Then $\Delta$ ...

**1**

vote

**1**answer

266 views

### Rational points of non-rational curves

An algebraic curve (in this question) is the zero set $C = f^{-1}(X\ Y)$ of any polynomial $f\in\mathbb R[X\ Y]$; we say then that $f$ represents $C$. ...

**2**

votes

**0**answers

232 views

### A problem in Galois Geometry

Given a prime $p$, out of $N$ vectors of length $p^k$ over $\Bbb F_2$ of Hamming weight $w^{k}$ that are chosen, how many vectors can there be with pairwise Hamming distance at least $2w^{k}$ given ...

**17**

votes

**0**answers

827 views

### Hrushovski's Construction

Zilber expressed a conjecture for $\aleph_{1}$- categorical theories (In the 80s).
Zilber's Conjecture: The geometry of any $\aleph_{1}$- categorical structure is one of the following:
(a) Trivial ...

**11**

votes

**3**answers

489 views

### Is there a nice way to “unravel” a great dodecahedron?

The great dodecahedron is a non-convex regular polyhedron bounded by 12 pentagonal faces, crossing each other, arranged in a star-shaped manner around each of its 12 vertices (see the Wikipedia page ...

**19**

votes

**2**answers

907 views

### Erdős, Harary, Tutte's “dimension of graph”: Progress in last 48 yrs?

I just ran across this delightful paper by an amazing triumvirate:
Paul Erdős, Frank Harary, and William Tutte. "On the dimension of a graph." Mathematika 12.118-122 (1965): 20.
(Cambridge link)
...

**12**

votes

**2**answers

565 views

### Sets of evenly distributed points in the Euclidean plane

Is there a set $P \subset \mathbb{R}^2$ of points in the Euclidean plane whose intersection
with every convex subset of $\mathbb{R}^2$ of area $1$ is nonempty but finite?
If the answer is yes, can ...

**7**

votes

**1**answer

202 views

### Can a tangle of arcs interlock in plane?

This is a variation of the question Can a tangle of arcs interlock?, asked by Joseph O'Rourke, and solved. I reproduce the question here:
Can a (finite) collection of disjoint circle arcs in ...