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

learn more… | top users | synonyms

2
votes
2answers
175 views

Primitive orthogonal vectors/Unimodular matrices

Primitive sets of vectors are very important in the theory of point lattices, since they constitute the sets of vectors that are part of a basis for the lattice. A set of integer vectors ...
6
votes
2answers
165 views

Untangling entwined rigid chains in 3-space

I am interested in exploring the degree of "tangledness" of two rigid chains in space. A polygonal chain is a simple (non-self-intersecting) path of segments in $\mathbb{R}^3$, viewed as a rigid body. ...
3
votes
1answer
141 views

Triangulation of the surface determined by sampling two of its cross-sections

I have a data set that essentially looks like the picture below, i.e., it's given by sets of points in $\mathbb{R}^3$ that sample the cross-sections of a certain surface that in principle I do not ...
7
votes
0answers
139 views

Fractional Helly for more than one piercing

Fractional Helly Theorem says the following: For every $0<\alpha\leq 1$ there exists $\beta = \beta(d, \alpha)$ with the following property. Let $C_1 , C_2 , ..., C_n$ be convex sets in $R^d$, $n ...
1
vote
1answer
199 views

Finding a point farthest away from $k$ points in a polygon

There are $k$ points placed inside a polygon and I am interested in finding a point inside the polygon (not necessarily on its boundary) who's minimum distance to any of the $k$ points is maximized. ...
11
votes
0answers
366 views

Does every connected set that is not a line segment cross some dyadic square?

A dyadic square is a subset of $R^2$ of the form $x + 2^{-n} [0,1]^2$ with $x \in 2^{-m} Z^2$, for integers $m,n \geq 0$. We say that a set $A$ crosses a square $S$ if there exists a connected subset ...
8
votes
0answers
102 views

Diameter of simplicial complex mirrored in property of Stanley-Reisner ring?

Consider a pure finite abstract simplicial complex $\Delta$. Define its diameter as the maximal distance between any two facets, i.e., between any two faces of maximal dimension $d-1$. The distance ...
17
votes
3answers
1k views

Research trends in geometry of numbers?

Geometry of numbers was initiated by Hermann Minkowski roughly a hundred years ago. At its heart is the relation between lattices (the group, not the poset) and convex bodies. One of its fundamental ...
2
votes
1answer
276 views

Apollonian gasket and the degree of convergence

Let $r_1,r_2\dots$ be the radii of Apollonian gasket. I would like to know for which values $\alpha$ we have $$\sum_{n=1}^\infty r_n^\alpha<\infty.$$ I know that if three circles $A$, $B$ and ...
1
vote
0answers
115 views

Spectrum of Combinatorial Laplacian

The spectrum of the combinatorial laplacian is well understood for a square lattice. What about for other lattices? In particular: Let $ f: \mathbb{Z}^2 \rightarrow \mathbb{R} $. The usual ...
23
votes
2answers
682 views

The kissing number of a square, cube, hypercube?

How many nonoverlapping unit squares can (nonoverlappingly) touch one unit square? By "nonoverlapping" I mean: not sharing an interior point. By "touch" I mean: sharing a boundary point. ...
2
votes
2answers
241 views

packing disks tightly in the plane

Given a discrete point set $S$ in ${\bf R}^2$ with a specified base-point $p_0 \in S$, label the remaining points as $p_1, p_2, \dots$ in order of increasing distance from $p_0$ (with ties resolved ...
3
votes
1answer
389 views

Combinatorial geodesics

[There has been a flaw in my definition - as Sergei and Andreas pointed out. I hope I could fix it.] I want to understand how the concepts of directions, straight (or shortest) lines, and geodesics ...
8
votes
1answer
346 views

Polyhedra that combinatorially shadow a sequence

Let $P$ be a polyhedron in $\mathbb{R}^3$. Say that $P$ combinatorially shadows a sequence of natural numbers $S$ if there is a continuous rotation of $P$ such that its orthogonal-projection shadows ...
0
votes
1answer
212 views

Is this bounded?

May be better to ask for help here. Let $v_{1}$, $v_{2}$, $\ldots$, $v_{m}$ be the vertices of a convex polygon in the plane and $v_{m+1}$ be a vertex in the interior of the convex polygon. Connect ...
13
votes
1answer
280 views

The optimal constant in Vitali covering lemma

Let me restate Vitali covering lemma. Let $\{B_i\}_{i\in F}$ be a finite collection of balls in the $\mathbb{R}^n$. Then there is $S\subset F$ such that the balls $\{B_i\}_{i\in S}$ are disjoint and ...
14
votes
2answers
669 views

Particles chasing one another around a circle

Two particles start out at random positions on a unit-circumference circle. Each has a random speed (distance per unit time) moving counterclockwise uniformly distributed within $[0,1]$. How long ...
1
vote
0answers
138 views

Lattice-point enumeration question involving linear combinations of matrices

I would like to know some references to learn more about an answer to this question, if there are any references: Let $A_1, \dots , A_m$ and $B$ be $n\times n$ symmetric matrices. Let $$S = \{(x_1, ...
1
vote
0answers
88 views

Rational viewing points in a polygon

We refer to the question posed in Seeing the vertices of a polygon with rational angles, but now ask for constructions or for the existence of rational viewing points. We'll call a point $p$ inside ...
5
votes
1answer
187 views

Seeing the vertices of a polygon with rational angles

Given any convex polygon in the plane, is it always possible to find a point $p$ in its interior such that when we draw the line segments from $p$ to each of its vertices, the angles formed at $p$ are ...
12
votes
1answer
280 views

The sparsest planar net that captures every unit segment

Let $\cal C = \lbrace C_i \rbrace$ be a collection of rectifiable curves in the plane with the property that every unit-length segment meets at least one curve in at least one point. Call such a ...
12
votes
1answer
551 views

The geometry of crinkled aluminum foil

I wonder if the geometry of crinkled aluminum foil has been studied?            The above is a photo of foil I flattened to reuse. It might be ...
4
votes
1answer
187 views

Best upper bound on rate for q-ary codes

Among the many upper bounds for families of codes in $\mathbb F _2 ^n$, the best known bound is the one by McEliece, Rodemich, Rumsey and Welch which states that the rate $R(\delta)$ corresponding to ...
0
votes
2answers
128 views

Disks Packing Variant

Usually disk packing problems require that no two disks of the packing intersect. Does anybody know if the problem has been studied when disks may intersect but they are not allowed to contain the ...
36
votes
8answers
3k views

A sudden smiley? :-)

This is a vague question, and I will no doubt be (properly!) chastised for posing it. I would like to generate a set $S$ of points in $\mathbb{R}^3$—$|S|$ finite or infinite—which has the ...
2
votes
2answers
177 views

Is there a simple test to determine whether a polytope is integral?

It is known that any rational convex polytope expressed as $\{ x\in\mathbb{R}^d : Ax \ge b \}$, where $A\in\mathbb{Z}^{k\times d}$ and $b\in\mathbb{Z}^k$, can be written as the convex hull of finitely ...
9
votes
2answers
506 views

Discrete Morse function from smooth one

Suppose I have a smooth manifold $M$ and a smooth Morse function $f$ on $M$. Is there a standard way to replace $M$ with a cell complex and $f$ with a discrete Morse function such the resulting ...
0
votes
3answers
271 views

The symmetry group of $\mathbb Z^d$

Let $d \ge 1$, and consider the integer lattice $\mathbb Z^d$. This is a homogeneous space, in the manner of the Erlangan Programm. I would like to write $\mathbb Z^d = G / H$, where $G$ is the ...
5
votes
0answers
393 views

Optimal Gear Trains

Suppose you need to slow down a turning motor so that a gear turns at an angular velocity $\frac{a}{b}$ of that of the motor shaft, where $a$ and $b$ are natural numbers. For example, this set of ...
6
votes
3answers
328 views

Herringbone partitions of regions and surfaces

Let $R \subset \mathbb{R}^2$ be a region of the plane bounded by a Jordan curve. The boundary $\partial R$ could be a polygon, or a smooth curve—there are variations depending upon boundary ...
3
votes
1answer
195 views

Empty convex polytopes for random point sets

I know of the famous results on the Erdős-Szekeres empty convex polygon problem in the plane (the Happy-Ending Problem), and I know that there are higher-dimensional extensions. A great source ...
11
votes
1answer
307 views

Detecting a hidden convex body with line probes

Imagine that, somewhere inside an origin-centered, unit-radius sphere $S$ in $\mathbb{R}^3$, sits a convex body $K$ of volume vol$(K)=\alpha (\frac{4}{3} \pi)$, with $\alpha < 1$ the fraction of ...
1
vote
2answers
187 views

Triangular grid with 4 edges per vertex

I am trying to create a triangular grid/mesh for a rectangular domain in $\mathbb{R}^2$ with the property that each vertex is shared by (at most) four edges. Is this possible to accomplish?
9
votes
1answer
461 views

Minimizing the excursion of a sum of unit vectors

I have $n$ unit-length vectors $v_i$ in $\mathbb{R}^3$, whose sum is zero: $$ v_1 + v_2 + \cdots + v_n = 0 \; .$$ Now I form the closed polygon $P$ in space by placing them head to tail. So the ...
9
votes
5answers
476 views

Minimal blocking objects with shadows like a cube

This is a more geometric version of the previous question, "Lattice-cube minimal blocking sets". I will first specialize to $\mathbb{R}^3$, $d=3$. View an $n \times n \times n$ cube $C_3(n)$ as ...
5
votes
2answers
235 views

Lattice-cube minimal blocking sets

Let $C_d(n)$ be the lattice cube consisting of the $n^d$ points with each of its $d$ coorindates in $\lbrace 1,2,\ldots,n \rbrace$. Define a blocking set for a lattice cube to be a set of points in ...
9
votes
4answers
722 views

Optimal pebble-packing shape

Suppose you throw many ($n$) congruent convex bodies (in $\mathbb{R}^3$) of unit volume (or of unit area in $\mathbb{R}^2$) into a large container, and shake it until little else changes. Q. ...
32
votes
6answers
962 views

Tetris-like falling sticky disks

Suppose unit-radius disks fall vertically from $y=+\infty$, one by one, and create a random jumble of disks above the $x$-axis. When a falling disk hits another, it stops and sticks there. Otherwise, ...
2
votes
2answers
477 views

Midpoint lattice polygons

Midpoint polygons (a.k.a Kasner polygons) have been studied, and their behavior is well understood. I am considering a variant, which I call midpoint lattice polygons. Start with a sequence of ...
8
votes
0answers
547 views

Building an $n$-toroid from cubes

I wonder if this has been studied: What is the fewest number of unit cubes from which one can build an $n$-toroid? The cubes must be glued face-to-face, and the boundary of the resulting ...
19
votes
6answers
2k views

Covering a unit ball with balls half the radius

This is a direct (and obvious) generalization of the recent MO question, "Covering disks with smaller disks": How many balls of radius $\frac{1}{2}$ are needed to cover completely a ball of radius ...
3
votes
2answers
300 views

Touching-tetrahedra graphs

Have the graphs representable by touching tetrahedra been explored? Let $\cal T$ be a collection of tetrahedra in $\mathbb{R}^3$ with pairwise disjoint interiors. Define a graph $G_{\cal T}$ to have ...
2
votes
1answer
180 views

Min Bend Orthogonal Knots

I am seeking literature on 3D orthogonal drawings of knots, especially minimum bend drawings. An orthogonal drawing employs segments parallel to the axes of a Cartesian coordinate system. A bend is a ...
10
votes
2answers
257 views

Acute triangulation

Assume that $S$ is a finite 2-dimensional simplicial complex equipped with a metric $d$ such that each triangle is isometric to a plane triangle (so $(S,d)$ is a polyhedral space). Is it possible ...
2
votes
1answer
147 views

Lipshitz Constant of the convex extension of a submodular function

The title says it all :) Given a submodular function (take the rank function of a matroid, for a concrete example) $f:\{0,1\}^n\rightarrow \mathbb{R}$, we can extend it to a convex function ...
2
votes
2answers
490 views

maximum number of shortest path among a set of n triangle obstacles

Assume that we have a two distinct points. The number of shortest path between these two points is one. When we add a triangle obstacle to the plane and this triangle intersects the line connecting ...
6
votes
1answer
307 views

Polygons that are hard to guard

Given an $n$-vertex polygonal 'art gallery' $P$ in the plane, it is possible to cover the interior of $P$ by placing 'guards' at (at worst) $\lfloor n/3\rfloor$ of the vertices of $P$. That this is ...
3
votes
1answer
291 views

Transience of self avoiding random walks on $\mathbb{Z}^d$

I'm finishing up a masters thesis in computer science and want to say a bit in the introduction about self-avoiding walks. My thesis looks at a random process which arose in computer science and my ...
0
votes
1answer
334 views

On the number of lines of given points

Hi all, I have a question Concerning Beck's theorem. I have read it from http://en.wikipedia.org/wiki/Beck%27s_theorem and I have two questions : I suppose Beck's theorem doesn't hold when instead ...
8
votes
1answer
411 views

Triangulations of polytopes and tilings of zonotopes

Consider a set $A = \{ a_1,a_2,\ldots, a_n \} $ of vectors in $\mathbb{R}^d$, which lie in a common affine hyperplane. Two convex polytopes may be obtained from $A$, namely the convex hull of the ...