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

learn more… | top users | synonyms

4
votes
2answers
96 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 ...
68
votes
5answers
5k views

Is there a dense subset of the real plane with all pairwise distances rational?

I heard the following two questions recently from Carl Mummert, who encouraged me to spread them around. Part of his motivation for the questions was to give the subject of computable model theory ...
6
votes
1answer
130 views

Minimizing deep holes in sphere packings

What's the current state of knowledge regarding packings of spheres in $n$-space that minimize the supremum of the sizes of the holes? This notion of tightness is more rigid than asymptotic density. I ...
11
votes
6answers
835 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. ...
5
votes
1answer
110 views

Ham sandwich theorem for discrete measures - reference request

A discrete version of the ham sandwich theorem states as follows (see for instance "Common Hyperplane Medians for Random Vectors" - Hill): For every $\mu_1,...,\mu_n$ discrete (i.e., purely atomic) ...
47
votes
3answers
4k views

What is the status of the Gauss Circle Problem?

For $r > 0$, let $L(r) = \# \{ (x,y) \in \mathbb{Z}^2 \ | \ x^2 + y^2 \leq r^2\}$ be the number of lattice points lying on or inside the standard circle of radius $r$. It is easy to see that $L(r) ...
3
votes
1answer
77 views

Covering points with a shortest lattice spiral

Let $S$ be a finite set of lattice points in $\mathbb{Z}^2$. My question is, roughly: Q. How can a shortest lattice spiral that passes through every point of $S$ be found? A lattice spiral (my ...
19
votes
5answers
1k views

What arrangement of unit cubes minimizes surface area?

For each of these two questions, one can assume that the arrangements are polycubes (for which a definition can be found in the excerpt-image below). Question A. How does one arrange $n$ unit cubes ...
9
votes
1answer
211 views

A random variation on Polya's orchard problem

Polya's orchard problem is as follows: "How thick must the trunks of the trees in a regularly spaced circular orchard grow if they are to block completely the view from the center?" See, ...
11
votes
1answer
287 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 ...
3
votes
5answers
222 views

Approaching convex and discrete geometry from other disciplines

I would like to learn some convex and discrete geometry (number 52 in MSC2010). I thought that it would be interesting to approach it from some other parts of mathematics - either by learning ...
0
votes
0answers
109 views

“Open Points” in the 1983 proof of Szemerédi-Trotter theorem

I was reading through the 1983 paper "Extremal Problems in Discrete Geometry" and I was confused about the definition of "open point" appearing in this paper. By this point in the paper, the authors ...
2
votes
2answers
312 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) ...
6
votes
1answer
291 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 ...
7
votes
1answer
87 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 ...
3
votes
0answers
115 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 ...
21
votes
1answer
976 views

Building a genus-$n$ torus 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 ...
2
votes
1answer
64 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
178 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) ...
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 ...
11
votes
2answers
2k views

Weighted area of a Voronoi cell

Let $X = \{ x_1,\dots,x_n\} $ denote a set of $n$ points in the unit square $S = [0,1]\times[0,1]$, and let $w = \{w_1,\dots,w_n\}$ denote a set of weights corresponding to the $n$ points in $X$. ...
2
votes
0answers
42 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
122 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
28 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 ...
8
votes
3answers
623 views

On maximal regular polyhedra inscribed in a regular polyhedron

Let T, C, O, D, or I be regular tetrahedron, cube, octahedron, dodecahedron, and icosahedron, respectively. Suppose that the outer polyhedron have edge-length 1. For example, it's easy to prove that ...
4
votes
1answer
108 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
306 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 ...
2
votes
0answers
123 views

A question on discrete numerical simulation on fluids mechanics

I read the paper "Stable, circulation-preseving simplicial fuids" by Elcott, et al: http://www.cs.jhu.edu/~misha/Fall09/Elcott07.pdf. It gives a structure preseving discretization of fluids. I have ...
8
votes
1answer
400 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
313 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$ ...
1
vote
1answer
154 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 ...
3
votes
1answer
534 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 ...
6
votes
1answer
133 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 ...
27
votes
1answer
888 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 ...
8
votes
1answer
180 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
209 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
55 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
48 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
72 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
89 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
269 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 ...
16
votes
3answers
2k views

How many unit squares can you pack into a rectangle with nearly integer side lengths?

Earlier today, somebody asked what looks like a homework problem, but admits the following reading which I think is interesting: Suppose $a_1,\dots, a_n$ are positive integers, and $\varepsilon$ ...
2
votes
1answer
108 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 ...
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 ...
5
votes
1answer
292 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
271 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
126 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 ...