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

learn more… | top users | synonyms (1)

4
votes
1answer
404 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
380 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
214 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
342 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
405 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
692 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
157 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, ...
2
votes
0answers
97 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
195 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
317 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
371 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
568 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
225 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
133 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
186 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
534 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
275 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
434 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
341 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
213 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
295 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
330 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
196 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
310 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
351 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
490 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 ...
7
votes
4answers
531 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
500 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
248 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
181 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
635 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
850 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
500 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
185 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 ...
10
votes
3answers
636 views

Combinatorial analogues of curvature

There appear to be many "combinatorial" definitions of curvature as applied to finite simplicial (or regular CW) complexes. For instance, we have the ideas of Cheeger, Muller and Schrader, of Forman ...
21
votes
1answer
1k 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 ...
13
votes
1answer
494 views

Partitioning the vertices of an n-cube with random hyperplane cuts

An evolutionary biologist asked me a question which boils down, at least in part, to what seems to me an interesting question of combinatorial/probabilistic geometry. It is an old chestnut of a ...
9
votes
0answers
295 views

How small parallelograms are we guaranteed to get, when we select the two sides from different plane lattices?

Title question description: Select two lattices $\Lambda_1$ and $\Lambda_2$ (here a lattice=additive free abelian group without accumulation points) of maximal rank two in the real plane. We normalize ...
3
votes
1answer
259 views

Grading a non-graded poset as squeezed as possible

Here is a curiosity question (motivated by the recent revamp of ranked-poset routines in Sage). Let $P$ be a finite poset. We look for a family $\left(a_p\right)_{p\in P}$ of real numbers summing up ...
21
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
325 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
0answers
129 views

A relation on triplets of points in the plane

This question is a follow up of my previous one (Planar sets closed under intersection of circles, Planar sets closed under intersection of circles) and is motivated by G. Zaimi's answer ...
2
votes
1answer
193 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 ...
1
vote
1answer
109 views

Generalizing the internal angle of a graph in $\mathbb{E}^2$ to $\mathbb{S}^2$

I am currently working on research involving packing problems and am finding myself needing the tools from Combinatorial Geometry (in particular, I've been reading Pach and Agarwal's book on the ...