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

learn more… | top users | synonyms (1)

14
votes
3answers
260 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
79 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
606 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
85 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 \mid c\in C \}$, for some $x\in R^d$, is called a homothetic copy of $C$. The ...
3
votes
1answer
117 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 ...
4
votes
3answers
559 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
151 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
37 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
340 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 ...
6
votes
1answer
258 views

When is a 0-1 matrix a one-intersection incidence matrix?

The following problem is what motivated my previous MO question. It is easily seen that for any given 0-1 matrix $M$, one can always find a set $\mathcal P$ of points, and a set $\mathcal C$ of ...
5
votes
0answers
424 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
334 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
138 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 ...
4
votes
1answer
209 views

convex polyhedron in the unit cube

Let $P$ be a given finite set of points within the $n$-dimensional unit cube. A finite set $Q$ of points within the $n$-dimensional unit cube covers $P$ if $\operatorname{conv}(Q) \supseteq P$ where ...
1
vote
1answer
108 views

Deducing Linear Inequalities

Let $X_1,X_2,\ldots,X_n $ be indeterminates. Denote by $S$ the set of all linear inequalities of the form $X_{i_1}+X_{i_2}+\ldots+X_{i_k} \geq k,$ with $k \in \{ 1,2,\ldots,n \}$ and $1 \leq i_1< ...
9
votes
1answer
305 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) ...
15
votes
2answers
334 views

Integer lattice points on a hypersphere

Is the following statement true? For every integer $n\ge2$ and every integer $k\ge0$ there exists a hypersphere in $\mathbb{R}^n$ (circle, sphere etc) containing exactly $k$ integer lattice ...
9
votes
1answer
364 views

Question about tetrahedron decomposition

Are there tetrahedra which can be subdivided into three non-overlapping parts similar to the original? I believe this would require splitting one face into three parts. I know some types of tetrahedra ...
2
votes
1answer
143 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
279 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
0answers
87 views

pavings and quadratic forms

Hi, let $L$ be a lattice isomorphic to $\mathbb{Z}^r$ for some positive integer $r$ and $E=L\otimes \mathbb{R}$. An integral paving in $E$ is a set $\Sigma$ of integral polytopes (the vertices are ...
3
votes
1answer
160 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 ...
10
votes
1answer
358 views

Fano plane drawings: embedding PG(2,2) into the real plane

By a drawing of the Fano plane I mean a system of seven simple curves and seven points in the real plane such that every point lies on exactly three curves, and every curve contains exactly three ...
9
votes
1answer
294 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
166 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 ...
2
votes
1answer
122 views

Realizability of extensions of a free oriented matroid by an independent set

Question: I am searching for a non-realizable matroid with few dependencies relative to the number of points. Precisely, I would like to find a non-realizable (over $\mathbb{R}$) oriented matroid $M$ ...
15
votes
1answer
348 views

Does every convex polyhedron have a combinatorially isomorphic counterpart whose all faces have rational areas?

Does every convex polyhedron have a combinatorially isomorphic counterpart whose faces all have rational areas? Does every convex polyhedron have a combinatorially isomorphic counterpart whose edges ...
3
votes
1answer
126 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, ...
12
votes
0answers
355 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 ...
5
votes
1answer
392 views

The Cayley Menger Theorem and integer matrices with row sum 2

I just filled a gap in my education by learning about the Cayley-Menger theorem, and the Cayley-Menger determinant: If $P_0, \dots, P_n$ are $n+1$ point in $\mathbb{R}^n$, and $d_{i,j} = |P_i - P_j|$ ...
2
votes
0answers
77 views

rigidity of isoradial graphs

Suppose given a $1$-separated net $\Gamma\subset\mathbb R^2$. Is it true or false that there exists $\delta>0$ and a $\delta$-isoradial graph containing $\Gamma$ as a subset of its vertices? (I am ...
27
votes
4answers
755 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 ...
4
votes
3answers
222 views

Perimeter/Neighborhood of a graph on grid

Hello, I have a $\sqrt{n}\times\sqrt{n}$ lattice graph $G=(V,E)$ i.e. vertices on said 2-dim integer lattice, and two vertices have an edge if their $L_1$ distance is one. Now I want to claim ...
2
votes
3answers
412 views

Strong notions of general position

Hi! I am looking for notions of general position that are stronger than linear general position. To illustrate, 3 points in linear general position don't lie on a line. I want a notion that would ...
1
vote
0answers
274 views

2d bin packing problem, with opportunity to optimize the size of the bin

I have been tasked with optimizing a manufacturing process. It is a non-trivial, NP hard problem. The problem is similar to the 2d bin packing problem, but we are trying to optimize the size of the ...
2
votes
0answers
88 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
177 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 ...
4
votes
0answers
120 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
287 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
208 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 ...
11
votes
2answers
771 views

Access to a preprint by D. N. Verma

Some work I am doing is connected with a sequence 1, 3, 40, 1225, 67956, $\dots$ which agrees with http://oeis.org/A012250 for all eight terms. The only useful information in OEIS on this sequence is ...
6
votes
2answers
172 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
147 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 ...
3
votes
1answer
199 views

What properties does generalized Delaunay triangulation have?

Suppose that instead of the usual circle, we pick some other convex set D and make the Delaunay triangulation of a finite planar point set with respect to this set, i.e. connect two points if there is ...
1
vote
1answer
287 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. ...
2
votes
1answer
240 views

Ways to look at a polyhedral graph

Motivation There are at least three interpretations of an abstract polyhedral (= planar 3-vertex-connected) graph: the 1-skeleton of a convex polyhedron (when embedded into $\mathbb{R}^3$) a ...
12
votes
0answers
420 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
118 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 ...