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

learn more… | top users | synonyms

1
vote
1answer
137 views

Practical use of estimates for the Gauss Circle Problem

This question is related to this and this ones. The Gauss Circle problem asks for the number $N(r)$ of integer points within a sphere of radius $r$ centered at the origin. It is well known that $N(r) ...
7
votes
1answer
75 views

Dropping altitudes to achieve nonobtuse planar triangulations: finite or infinite?

Given a planar triangulation of (say) a convex region, imagine the following process to convert it to a triangulation with no obtuse angles: Pick an arbitrary obtuse angle at vertex $a$ of ...
2
votes
1answer
59 views

Characterization of the medial axis of a surface

I would like to know if the following "characterization" of the medial axis of a surface is correct, and if so, how to prove it. Let $S$ be a continuous, piecewise smooth, compact surface embedded in ...
5
votes
1answer
171 views

Small remarkable matroids

Working on phased matroids (a generalization of oriented matroid to the complex case) I've found an interesting formula for computing the inner Tutte group (and, hence, all the Tutte groups) ...
2
votes
0answers
36 views

Looking for N-dimensional spheres in the configuration space of the colorful Tverberg problem

Here we use standard notation for Tverberg's theorem: Dimension $d$, number of partition blocks $r$, and $N=(r-1)(d+1)$. The configuration space of Tverberg's theorem is the simplicial complex ...
2
votes
1answer
119 views

Regarding the set up of a geometry of numbers lemma

I have a question related to geometry of numbers, which although seems quite basic, I was rather confused by it so I decided to ask here. Let $\Lambda$ be a lattice in $\mathbb{R}^n$. Let $R_1, ..., ...
1
vote
0answers
26 views

Moment lemma for circular arc polygons

A "moment lemma" originally due to Fejes Tóth (I guess) states that if $P$ is any polygon (in $\mathbb{R}^2$) with $k$ sides, then for any $\mathbf{y}$, we have ...
4
votes
1answer
94 views

The number of facets of a polyhedron under linear transformation

Consider a (not necessarily bounded) convex polyhedron $P\subset \mathbb{R}^n$ which has $k$ facets. Let $L:\mathbb{R}^n \to \mathbb{R}^m$ be a linear transformation. Question1: Is there a fixed ...
5
votes
1answer
273 views

Linear transformation of a polyhedron

Is there a simple proof that shows: Linear transformation of a $\mathcal{H}$-polyhedron (i.e. the intersection of finitely many closed half-spaces) is a $\mathcal{H}$-polyhedron. Minkowski sum of ...
8
votes
1answer
397 views

Polyhedron not circumscribed about a sphere

Let $P$ be a polyhedron whose faces are colored black and white so that there are more black faces and no two black faces are adjacent. Show that $P$ is not circumscribed about a sphere. My teacher ...
11
votes
1answer
308 views

Longest of random worm-like paths in $\mathbb{Z}^2$

Imagine at each lattice point of $\mathbb{Z}^2$ within $[1,3n]^2$, with coordinates $\equiv 2 \mod 3$, we place, with equal probability, one of these six patterns:       The result ...
0
votes
0answers
42 views

Paths on Cartesian products of graphs satisfying linear constraints

Assume integers $d > r > 0$ and a connected graph $G$ with $d$ vertices. Every point on the $r$-fold Cartesian product of $G$ with itself, $G^{\square r}$, is equivalent to a dimension-$d$ ...
2
votes
1answer
66 views

Discrete gradient on point clouds

I am interested to know some ways to approximate discrete gradient if you have a function on point clouds in 2D or 3D. If you have a function defined on a grid, it well known that you can use a ...
1
vote
1answer
148 views

Positroids and Totally Nonnegative Complex Grassmanian

Recently I begin working on matroids, in particular to a generalization of oriented matroids to the complex case. I found on arxiv the following interesting articles: 1)Alexander Postnikov: Total ...
6
votes
1answer
131 views

Hiding $k$ disks inside a larger disk

Suppose one has $k$ unit-radius disks, and the goal is to hide them inside a disk of radius $R \gg k$. The detection probes are rays along a line. (Think of the disks as tumor cells, and the rays as ...
8
votes
1answer
176 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
202 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 ...
0
votes
1answer
53 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 ...
1
vote
0answers
44 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 ...
1
vote
1answer
70 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
84 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
262 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
107 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
285 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
262 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
34 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
118 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 ...
3
votes
3answers
91 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 ...
27
votes
1answer
871 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 ...
6
votes
1answer
244 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
152 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
40 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 ...
3
votes
2answers
121 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
110 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 ...
7
votes
2answers
251 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
162 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 ...
3
votes
1answer
521 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
467 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
348 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
361 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
197 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
53 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
747 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
108 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
189 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
152 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
131 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
429 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
329 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
327 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 ...