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

learn more… | top users | synonyms (1)

1
vote
0answers
124 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 ...
2
votes
2answers
219 views

Is there a combinatorial analogue of the Kazdan Warner theorem?

First let me state a result of Kazdan and Warner Let $M$ be a compact orientable two dimensional manifold. Let $f:M \rightarrow \mathbb{R}$ be a function that has the same sign as the Euler ...
25
votes
3answers
1k views

Can one recover the smooth Gauss Bonnet theorem from the combinatorial Gauss Bonnet theorem as an appropriate limit?

First let me state two known theorems. Theorem 1 (for smooth manifolds): Let $(M,g)$ be a smooth compact two dimensional Riemannian manifold. Then $$ \int \frac{K}{2 \pi} dA = \chi (M) $$ where $K$ ...
23
votes
2answers
816 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. ...
8
votes
2answers
558 views

A Problem about partitioning $S^2$

Question: Can the 2-dimensional sphere $S^2$ be partitioned into four nonempty sets such that every circle in $S^2$ passes through just three of these four sets? Here, "just three" means "exactly ...
21
votes
1answer
716 views

Sane bound on number of moves for Maker-Breaker game on $\mathbb R^2$ for $\{0,1,2,3,4\}$

The description below comes from József Beck. Combinatorial games. Tic-tac-toe theory, Encyclopedia of Mathematics and its Applications, 114. Cambridge University Press, Cambridge, 2008, MR2402857 ...
2
votes
2answers
252 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 ...
2
votes
2answers
227 views

What is the smallest number of subsets in such a subdivision?

Given any $30$ points in the plane, what is the smallest number of subsets in a subdivision of the set of $30$ points into subsets such that all the points in each subset are on the boundary of the ...
4
votes
1answer
415 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
403 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
215 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 ...
9
votes
2answers
344 views

On well separated point sets in the plane

Let us say that a finite set $A$ in the plane is $1$-separated if: 1) it has an even number of points; 2) no open ball of diameter $1$ contains more than $|A|/2$ points. For a $1$-separated set $A$ ...
14
votes
1answer
456 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
727 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
169 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, ...
9
votes
3answers
384 views

Mutually tangent ellipsoids in 3 space

I recently heard a claim that for any n, it is possible to arrange n ellipsoids in 3 space such that each pair of ellipsoids is kissing. Is this true, and if so, how? Edit: By kissing, I mean that I ...
2
votes
0answers
98 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 ...
6
votes
1answer
196 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 ...
13
votes
1answer
341 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 ...
11
votes
0answers
385 views

Reciprocity (Ehrhart-style) for real polytopes?

Is there some sense in which the well-known Ehrhart reciprocity law for rational, convex, polytopes can be extended to any convex polytope with arbitrary real vertices? In other words, given any ...
12
votes
1answer
579 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
264 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 ...
1
vote
2answers
137 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 ...
37
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
194 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 ...
11
votes
2answers
566 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
277 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 ...
9
votes
2answers
892 views

The Gauss circle problem on a hexagonal lattice

Take an infinite hexagonal lattice (or equivalently, an equilateral triangular lattice), with unit spacing between the closest lattice point pairs, and draw a disc of radius $r$ centered on a lattice ...
5
votes
0answers
479 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
347 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
230 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 ...
4
votes
2answers
308 views

Realization spaces for regular convex polytopes

Q1. Are there convex polytopes combinatorially equivalent to each of the regular polytopes that are realized with integer vertex coordinates? ...
11
votes
1answer
336 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 ...
7
votes
1answer
2k views

Get Largest Inscribed Rectangle of a Concave Polygon

I'm looking for an algorithm to find a set of largest inscribed rectangles of a concave polygon where each rectangle must be collinear with one of the edges of the polygon. In other words, I want to ...
8
votes
2answers
2k views

Covering a Polygon with Rectangles

I am tyring to cover a simple concave polygon with a minimum rectangles. My rectangles can be any length, but they have maximum widths, and the polygon will never have an acute angle. I thought about ...
1
vote
2answers
197 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?
5
votes
0answers
318 views

$n$ lines in a general position and the number of empty triangles

Question. Consider $n \geq 5$ lines in a general position (i.e. no two lines are parallel and no triple intersections are allowed) in $\mathbb{R}^2$. Let $T(n)$ denote the maximal number of empty ...
3
votes
2answers
361 views

What collections of convex sets result in non-trivial uses of Helly's theorem?

Consider Helly Theorem, taken from notes by Igor Pak: Let $X_1, \dots, X_n \in {\mathbb{R}}^2$ be convex regions in the plane such that any triple interesects $X_i \cap X_j \cap X_k \neq 0$. Then ...
9
votes
1answer
514 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 ...
8
votes
4answers
576 views

Knot diagrams, sets of moves and equivalence relations

Short version: Does anyone study equivalence classes generated by a given set of "moves" (in the sense of, but not limited to, Reidemeister moves) on the set of knot diagrams? Yes, I understand that ...
9
votes
5answers
513 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
265 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 ...
4
votes
0answers
183 views

Mean number of $n$-simplices per $(n-2)$-simplex in a triangulated $n$-manifold

Work by Tamura (extending results by Luo and Stong) shows the following. Theorem: For any closed 3-manifold $M$ and any rational number $4.5 < r < 6$ there is a triangulation $T$ of $M$ for ...
19
votes
1answer
685 views

Monomer-Dimer tatami tilings need better relationships with other math. Summary of results.

A monomer-dimer tiling of a rectangular grid with $r$ rows and $c$ columns satisfies the \emph{tatami} condition if no four tiles meet at any point. (or you can think of it as the removal of a ...
0
votes
1answer
81 views

When do there exist locally regular embeddings of regular graphs?

I don't know how one can tackle the following kind of question, so any hint is welcome. I formulate a precise question in order to fix ideas, but it is to be considered as an example out of a more ...
12
votes
6answers
901 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. ...
35
votes
6answers
1k 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
517 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 ...
2
votes
1answer
115 views

Graph implemened into the plane with segments as edges and we search for matching with no edges intersecting

There are some points in the plane and some of them are connected with segments between them. We look at this structure as a graph implemented into the plane where the points are the vertices and the ...
4
votes
2answers
188 views

Generators of a 2D lattice

Dear MO_World, I'm hoping someone can point me towards a reference for something. I have an invertible $2\times 2$ matrix, $A$, with real entries such that for both of the rows, the entries are ...