Finite or discrete collections of geometric objects. Packings, tilings, polyhedra, polytopes, intersection, arrangements, rigidity.

learn more… | top users | synonyms (1)

8
votes
1answer
297 views

Billiard dynamics with angle of reflection a fraction of angle of incidence

Suppose that a billiard ball bouncing in a unit square (or a lightray reflecting in a mirrored square) has the property that the angle of reflection is a fraction of the angle of incidence, rather ...
9
votes
1answer
360 views

Are there irregular tilings by L-polyominoes?

I wonder if one can tile the plane with an order-$n$ L-polyomino in a fundamentally irregular manner. I seek help in defining what should constitute "irregular." An L-polyomino of order $n \ge 2$ is ...
2
votes
1answer
90 views

mean length of the non-crossing graphs on n points

My original question is rather vague so I'll start with a precise example and then indicate possible generalisations. Given a n-tuple $x=(x_1,\dots,x_n)$ in, say, a square with side-length $1$ in the ...
3
votes
1answer
106 views

Polygonal Venn diagrams

Suppose that the interiors of $n$ $m$-sided planar simple closed polygons generate a $\sigma$-algebra $A$. How many atoms can $A$ possess, at the most? Failing an exact answer, how about good ...
1
vote
0answers
55 views

Approximating Unit covering of d-dimensional points

Given a $d$-dimensional disk of radius $2$ in $\mathbb{R}^d$, how many disks of radius $1$ suffice to cover it. Of course, it's fine if the smaller disks overlap. What matters is to specify a finite ...
7
votes
2answers
164 views

Uniqueness of an equilateral triangle decomposition into three similar polygons, exactly two congruent

A favorite fun problem I give to students and (even non-mathematical) friends is the following: Find a decomposition of an equilateral triangle into three similar polygons, exactly two of which are ...
1
vote
1answer
73 views

Unit covering of $d$-dimensional points

Given a set of points in $X$ axis, we want to cover them with minimum number of unit intervals. For this problem we can assume that each interval in the optimal solution is starting or ending in one ...
2
votes
1answer
118 views

Bound on maximum distance between points on a unit N-Sphere

I want to select M points on the N-sphere such that $min_{i\neq j,i,j\in \{1..M\}} ||x_i - x_j||$ is maximized. Are there good upper bounds for this max-min distance?
7
votes
2answers
277 views

Wait time to grid network disconnection with failing edges

Let $G_n$ be an $n \times n$ planar toroidal grid graph, with each node connected to its four neighbors, with the top row connected to the bottom, and the right column connected to the left. Suppose ...
2
votes
1answer
123 views

The Mahler conjecture and non-zonoidal 3-polytopes (4-polytopes)

I have been working on the Mahler conjecture for over a year now and have made some progress for certain classes of convex polytopes and I'm now attempting to write up my results specified to ...
5
votes
1answer
320 views

A result from Peter McMullen's thesis

The classical definition of regular polytopes is recursive. It says that a polytope is regular if its facets and vertex figures (both smaller-dimensional polytopes) are regular. The modern definition ...
14
votes
0answers
300 views

Knight's tours in higher dimensions

I wonder if Knight's Tours have been explored in higher dimensions, using the following definition of a knight move. In dimension $d=2$, the knight moves left/right and forward/back one step and two ...
1
vote
1answer
35 views

Maximum crossings of curvature-constrained curve

Let $C$ be a curve in the plane whose curvature is everywhere $\le 1$. If $C$ has length $L$, what is the largest number of proper self-crossings of $C$ as a function of $L$? For example, the curve ...
1
vote
1answer
145 views

Calculate the discrete set of points B which are in the convex hull of the set of points A

This problem is likely best described with the following picture: Given the discrete set of points $A$ (shown in blue), I wish to calculate the discrete set of points that are contained within the ...
12
votes
3answers
626 views

Is {6,3,7} an 'ultrahyperbolic' Coxeter group?

These pictures, drawn by Roice Nelson, are attempts to visualize a geometry having as symmetries the {6,3,7} Coxeter group, by which I mean the one coming from the Coxeter diagram ...
3
votes
3answers
100 views

Minimal area of non-planar lattice curves

Consider a $\mathbb{Z}^d$ lattice whose edges connect nearest-neighbor sites only, i.e. a $d$-dimensional hypercubic grid. Let $C$ be a closed curve along such edges. In general, for $d>2$ such ...
28
votes
1answer
998 views

Can we find lattice polyhedra with faces of area 1,2,3,…?

I asked this question two months ago on MSE, where it earned the rare Tumbleweed badge for garnering zero votes, zero answers, and 25 views over 61 days. Perhaps justifiably so! Here I repeat it with ...
2
votes
0answers
90 views

What is the projective dual of a planar graph?

Everybody learns the usual definition of the dual of a planar graph when edges are preserved and faces are mapped to vertices. Everybody learns the projective duality. What if we apply it to a ...
7
votes
1answer
362 views

Triangle (constrained number, rather than shape) packing?

Are there any interesting results on optimal packings in the plane using a fixed number of triangles (without a fixed size or shape constraint)? For instance, what's the maximum area packing of the ...
6
votes
1answer
171 views

Integral straight-line embeddings of planar graphs

Wikipedia says (in the article on Fáry's theorem), "Heiko Harborth raised the question of whether every planar graph has a straight line representation in which all edge lengths are integers. The ...
1
vote
0answers
52 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 ...
4
votes
2answers
140 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 ...
2
votes
1answer
115 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 ...
8
votes
2answers
595 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
0answers
174 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 ...
0
votes
0answers
111 views

Generalized Sphere Kissing Problem

I am currently researching discrete geometry and I am in need of an upper bound on a generalized kissing number in 3-dimensions dependent upon a parameter $\eta$ which is the radii of spheres touching ...
2
votes
1answer
595 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 ...
14
votes
2answers
478 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}, ...
1
vote
1answer
362 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 \}$. ...
18
votes
2answers
378 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
2answers
225 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
1answer
107 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
1answer
61 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
2answers
791 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
2answers
117 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
1answer
319 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
2answers
162 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
1answer
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
2answers
524 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
3answers
372 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
2answers
332 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
1answer
220 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
3answers
310 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
5answers
444 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
2answers
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
0answers
73 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
1answer
240 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
0answers
101 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
0answers
514 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
3answers
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 ...