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

learn more… | top users | synonyms

14
votes
3answers
237 views

Covering a hexagon

For $\epsilon > 0$ sufficiently small, can a regular hexagon with sides of length $1 + \epsilon$ be covered by seven equilateral triangles with sides of length $1$? Motivation: Conway and Soifer ...
7
votes
0answers
68 views

Is the equidissection spectrum closed under addition?

If a polygon can be cut into $m$ as well as into $n$ triangular pieces of equal area, can it also be cut into $m+n$ triangles of equal area? (I'm editing after realizing that my conjecture that a ...
11
votes
3answers
593 views

What fraction of n-point sets in the unit ball have diameter smaller than 1?

This question is inspired by a recent talk by Matt Kahle on random geometric complexes. Some simple notation: let $\mathcal{B} \subset \mathbb{R}^d$ be the unit ball in $d$-dimensional Euclidean ...
2
votes
1answer
62 views

Covering the annulus of d-cube

Given a convex body $C\subset R^d$ and a positive real $\lambda$, any set of the form $\lambda C+x$ = {$~\lambda c+x|c\in C$} for some $x\in R^d$ is called homothetic copy of $C$. The number ...
3
votes
1answer
102 views

Covering a convex body with its smaller homothetic copies

Given a convex body $C\subset R^d$ and a positive real $\lambda$, any set of the form $\lambda C + x = \{ \lambda c + x \mid c\in C \}$ for some $x\in R^d$ is called a homothetic copy of $C$. The ...
3
votes
2answers
291 views

Consecutive Integer Squared Square

Is it possible to construct a squared square out of consecutive integer squares? Be it 1,2,3,...n or k,k+1,k+2,...n.
45
votes
5answers
2k views

If a unitsquare is partitioned into 101 triangles, is the area of one at least 1%?

Update: The answer to the title question is not necessarily, as pointed out by Tapio and Willie. I would be more interested in lower bounds. Monsky's famous and amazingly tricky proof says that if we ...
1
vote
1answer
148 views

Helly's number from biconvex functions

Helly's Theorem states the following. Suppose $X_1,X_2,...,X_N$ are convex sets in $\mathbb{R}^d$, such that for any index-set $I$ with $|I| \leq h(d) := d+1$, we have $\bigcap_{i \in I} X_i \neq ...
0
votes
0answers
36 views

Covering the annulus of symmetric convex body

Consider a symmetric convex body $A$ in $R^d$. Now, we draw another object, $A'$, concentric and translated with respect to A and having radius slightly greater than twice to the radius of $A$. Now ...
4
votes
1answer
262 views

Algorithms for covering a rectilinear polygon using the same multiple rectangles

Sorry for the crossing-posting: original post is here All angles of the polygon (representing a room) are right. It may be convex or concave. Use rectangles of the same size (representing a sensor ...
5
votes
0answers
383 views

N-balls covering n-balls

This question is a follow-on question from: Covering a unit ball with balls half the radius The questions are these: Given an arbitrary dimension d, and a unit n-ball in d-dimensional Euclidean ...
7
votes
0answers
327 views

Rectangology and squareology

I thought that rectangles were simple, and squares even simpler. Until my research has led me to several questions about rectangles and squares, which I can't solve. I started by posting this ...
2
votes
1answer
137 views

Helly's Theorem for Biconvex Sets

Helly's Theorem states the following. Suppose that $X_1,X_2,...,X_N$ are convex sets in $\mathbb{R}^d$, such that for any index-set $I$ with $|I| \leq h(d) := d+1$, we have $\bigcap_{i \in I} X_i \neq ...
9
votes
1answer
298 views

Needle probing for a convex body

Suppose there is an unknown closed convex body $K$ of volume vol$(K) = V$ inside the unit cube $[-\frac{1}{2}, \frac{1}{2}]^d$ in $\mathbb{R}^d$. You are permitted to probe with a (one-dimensional) ...
8
votes
1answer
287 views

Question about tetrahedron decomposition

Are there tetrahedra which can be subdivided into three parts similar to the original? I believe this would require splitting one face into three parts. I know some types of tetrahedron for which this ...
2
votes
1answer
136 views

Is this cube packing possible?

I know how to pack $5$ unit squares in a square of side length $2+\frac{\sqrt{2}}{2}$. Is there an $\varepsilon>0$ such that there exists a packing of $9$ unit cubes in a cube of side length ...
2
votes
1answer
217 views

Regularity of Delaunay triangulation of a hypercube

First using a three dimensional unit cube as an example for the term "regularity", we can have two possible triangulations: (A) (B) We say the lower triangulation is more "regular" than upper ...
3
votes
1answer
148 views

Simplex with edges of length at least s having smallest circumradius

Is it true that of all $n$-simplices with edge lengths greater than or equal to some parameter $s$, the regular simplex with edge lengths $s$ has the smallest circumradius? It seems obvious, but I ...
9
votes
1answer
265 views

Maximum number of Vertices of Hypercube covered by Ball of radius R

Let $R>0$ be given and let $H^n$ be the unit hypercube in $\mathbb{R}^n$. The problem I am facing is to find the maximum number of vertices of $H^n$ which can be covered by a closed $n$-dimensional ...
0
votes
1answer
150 views

Counting integer points in a Minkowski sum

We have known from Ehrhart theory that if $P$ is a $d$-dimensional polytope of $\mathbb R^n$ which has integer vertices then the number of integer points in $nP$ is a polynomial of degree $d$. We also ...
3
votes
1answer
113 views

The discrete theory of compressible fluids dynamics

I am working on the discrete theory of compressible fluids dynamics, i.e., numerically solving and simulating the compressible fluids , we are interested in the way using discrete exterior calculus, ...
11
votes
0answers
333 views

Drawings of complete graphs with $Z(n)$ crossings

Hill conjectured that the minimum number of crossings in a drawing of the complete graph $K_n$ in the plane is exactly $$Z(n) = \frac{1}{4} \bigg\lfloor\frac{n}{2}\bigg\rfloor ...
27
votes
4answers
734 views

Can every $\mathbb{Z}^2$ disk be pinball-reached?

Let every point of $\mathbb{Z}^2$ be surrounded by a mirrored disk of radius $r < \frac{1}{2}$, except leave the origin $(0,0)$ unoccupied by a disk. Q. Is it the case that every disk can be ...
2
votes
0answers
86 views

Symmetric dominance regions surrounding a Gaussian prime

Let $z=a + b i$ be a complex number which is a Gaussian prime, on neither the $x$- nor the $y$-axis. So $a^2+b^2$ is a prime. Construct a region $D(z)$ surrounding $z$ which is the largest ...
2
votes
1answer
169 views

Maintaining boundary of unit circle arrangement

I have a process which in each step creates a new unit circle and I am interested in maintaining the boundary of the resulting arrangement in linear time. Is there anything known about computing this ...
3
votes
0answers
116 views

Graph drawing maximizing the volume of the convex hull

Given a graph $G=(V,E)$ and a length function $\ell:E\to\mathbb{R}_+$. An embedding of the graph into the $d$-dimensional Euclidean space is a map $f:V\to\mathbb{R}^d$ such that ...
3
votes
2answers
247 views

Questions on Discrete Exterior Calculus in numerial computing

I have several questions about the Discrete Exterior Calculus (DEC) in the numerical method for solving partial differential equation in physics: (Discrete Exterious Calculus is the newly developed ...
2
votes
2answers
185 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
169 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
140 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
222 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
380 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
110 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
295 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
706 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
245 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
393 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
359 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 ...
13
votes
1answer
324 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
682 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
149 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
91 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
189 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
287 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
557 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
193 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 ...