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

learn more… | top users | synonyms (1)

5
votes
2answers
324 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
217 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
144 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 ...
5
votes
1answer
186 views

Light inside a polyhedron

I have two questions the same as Mostafa's Question: Visibility of vertices in polyhedra Suppose $P$ is a closed polyhedron in space (i.e. a union of polygons which is homeomorphic to $S^2$) and $X$ ...
20
votes
3answers
891 views

Visibility of vertices in polyhedra

Suppose $P$ is a closed polyhedron in space (i.e. a union of polygons which is homeomorphic to $S^2$) and $X$ is an interior point of $P$. Is it true that $X$ can see at least one vertex of $P$? More ...
8
votes
1answer
357 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
408 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
99 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
113 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
56 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
172 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
78 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
139 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
281 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
130 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
322 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
318 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
38 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 ...
2
votes
1answer
160 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
662 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
106 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
1k 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
95 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 ...
8
votes
1answer
402 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
184 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
54 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
117 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
827 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 ...
14
votes
2answers
419 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
118 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
632 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
490 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}, ...
2
votes
1answer
367 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
388 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
241 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
115 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
67 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
808 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
121 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
335 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
172 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
134 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
569 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
399 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
336 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 ...
4
votes
1answer
225 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
317 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
469 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 ...