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

learn more… | top users | synonyms (1)

0
votes
0answers
9 views

What is the 4D axis of rotation for Necker cube inversion? [migrated]

See the figure on top of page 47 of Rudy Rucker's book. ...
2
votes
2answers
143 views

Number of ways of tiling a $2 \times n$ rectangle using rectangles with integer sides

How many ways are there of tiling a $2 \times n$ rectangles using rectangular tiles with positive integer side lengths? I've done some work on this and have found a way of calculating this that's ...
4
votes
0answers
112 views

Reference for the notion of polyhedra “degenerations”

Let $P$ be a convex polyhedron and let $P(t)$ be a continuous deformation thereof, such that: a) $P(0)=P$; b) for all $t\in[0;1)$ the polyhedron $P(t)$ is strongly combinatorially equivalent to $P$ ...
0
votes
0answers
21 views

Non-adjacent Pair of Edges with Minimal Weight Sum

Given an weighted, undirected Graph $G(V,E)$ without loops or parallel edges, what is the complexity of determining a pair of non-adjacent edges, whose sum of weights is w.l.o.g. minimal? ...
2
votes
1answer
79 views

Orthogonal embeddings and edge lengths

I'm interested in orthogonal embeddings of graphs into the 2-dimensional, i.e where vertices are placed at integer co-ordinates and edges are routed along the grid lines and are not allowed to ...
2
votes
0answers
138 views

Polynomials representing locally constant functions

Let $K$ be a finite field with $p$ elements. (a) Let $f\in K\lbrack x\rbrack$ be such that (i) $\deg(f)<p$ and (ii) $f(2x) = f(x)$ for $\geq (1-\epsilon) p$ values of $x$ in $K$. What can we say ...
2
votes
0answers
48 views

Sharpening the Loomis-Whitney inequality

The Loomis-Whitney inequality implies that if $A\subset\mathbb Z^n$ is a finite, non-empty set of size $K:=|A|$, then, denoting by $K_1,\dotsc,K_n$ the sizes of the projections of $A$ onto the ...
0
votes
0answers
30 views

Question on solving an optimization problem using Variable splitting and ADMM

Tell me if I have found the right approach to the following optimization problem: $$ min_{x} \frac{1}{2}\left \| Ax-b \right \|_2^2 \\ s.t. \ \ \Phi v=x \ , \ {x^T(1-x)}=0 $$ $A$ and $\Phi$ ...
3
votes
0answers
71 views

Is there a Havel-Hakimi for geometric graphs?

Suppose that we are given $n$ points in the plane, with a degree prescribed for each, and the question is whether we can place a geometric graph on them. Is there an efficient algorithm for this? ...
1
vote
0answers
54 views

Building an orthogonal embedding for a 4-planar graph

I'm interested in the following paper http://www.computer.org/csdl/trans/tc/1981/02/06312176.pdf In particular i'm interested in the construction Valiant describes to prove that it is possible to ...
5
votes
5answers
212 views

Locked convex polyhedra

Call a set of polyhedra free if it is possible to rigidly move the polyhedra, without any polyhedron intersecting any other, so that their pairwise distances are arbitrary large, and locked otherwise. ...
5
votes
0answers
52 views

convex hull of all-ones principal submatrices

For a subset $S$ of $\{1,\ldots,n\}$, let $\mathbf{1}_S\in\{0,1\}^n$ denote the indicator vector of $S$, with a $1$ on the $i$th coordinate iff $i\in S$. Let $\mathcal{X}$ denote the convex-hull of ...
2
votes
0answers
51 views

Characterizing subgroups of R^n with dense factors

It is well known that (additive) subgroups of $\mathbb{R}^n$ are products of discrete subgroups (lattices) by dense subgroups in subspaces. My question is the following: given a generator set of $p$ ...
3
votes
2answers
106 views

How many different integer polytopes does square lattice have?

Let $E_n = \{ (i,j) : 0 \leq i,j \leq n-1 \}$. We say that a polytope $P$ is an integer polytope in $E_n$ if all vertices of $P$ belongs to $E_n$. My question is how many different integer polytopes ...
12
votes
1answer
336 views

On convergence of convex bodies

Let $K\subset \mathbb{R}^n$ be a compact convex set of full dimension. Assume that $0\in \partial K$. Question 1. Is it true that there exists $\varepsilon_0>0$ such that for any ...
0
votes
0answers
16 views

min-max problems about sets of points

Many research problems in discrete geometry have the following form: Given a set $S_n$ of $n$ points, let $Max(S_n)$ be the maximum [something]. Define: $$MinMax(n) = \inf_{S_n} Max(S_n)$$ ...
3
votes
0answers
72 views

Algorithm for finding the fewest cartesian products to partition a set of points

The question Algorithm for finding the fewest rectangles to cover a set of rectangles was already answered here and a similar question was answered here. Those questions were about regular geometric ...
2
votes
1answer
89 views

What is the maximal diameter of a cell in a particular partition of the simplex?

Consider a standard simplex with points $(p_1, \dots, p_n)$, $p_i \ge 0$, and $\sum_i p_i = 1$. Fix a set $\{q_k\}_{k=1}^K$ with $0\leq q_k \leq \infty$ and $i,j\in\{1, \dots, n\}$. Partition it via ...
6
votes
1answer
171 views

Exotic line arrangements

I would like to discuss about the following problem. Hopefully, you will suggest me some ideas and bibliography. At first I provide some basic definitions to set up the notation. Let us consider a ...
10
votes
1answer
215 views

Optimization of points on a plane

Suppose we have $n$ points on a plane. Let $D$ be the sum of the squares of all the pairwise distances between the points. Let $A$ be the area of the convex hull. What is the minimum possible value of ...
2
votes
1answer
106 views

Is it possible to cover all pairs of points at distance at most 1 by constant number of partitions into sets of diameter at most 1?

Let $n$ be a natural number and let $S_n$ be a square $[0,n] \times [0,n]$ in the plane. We say that a partition $\mathcal{Q} = R_1 \cup \cdots \cup R_t$ of $S_n$ is simple if each of the sets $R_1, ...
1
vote
0answers
42 views

VC dimension of infinite cones [closed]

What is the VC dimension of infinite $d$-dimensional cones? ( single cones not double). I would say $2d + 1$ or $O(d^2)$ Does anybody have any reference or ideas?
0
votes
0answers
19 views

Is there a shelling of a (threshold)shifted complex, such that any partial shelling is still (threshold)shifted?

first the relevant definitions: A complex $\Delta \subset 2^{[n]}$ is a family of subsets of $[n]$ that is closed downwards, i.e. if $A \subset B$ and $B \in \Delta$, then $A \in \Delta$. A complex ...
0
votes
0answers
55 views

What is the minimal number of lines needed to partition a simplex into cells of diameter at most $\epsilon$?

I am studying a problem that requires me to partition the simplex into cells using a particular family of hyperplanes. For concreteness, consider the 2-simplex. I would like to construct lines ...
7
votes
1answer
192 views

Unusual isoperimetry and maximizing the measure of unions of translates of a set

Let me state a standard result first. Let a $A\subset \mathbb{R}^d$ be a set of fixed volume. Define $A_t$ to be the set of all points at distance at most $t$ from $A$. Then the volume of $A_t$ is ...
5
votes
2answers
265 views

Conjugate transpose and discreteness, for Kleinian groups

Let $G=\langle g_1,\dots g_n\rangle<\mathrm{PSL}_2(\mathbb{C})$ be discrete, i.e. a finitely generated Kleinian group. Let $H=\langle g^{\dagger}g\mid g\in G\rangle$, (the group generated by the ...
4
votes
1answer
268 views

Generating function for number of different tessellation checkered rectangle

Let $R_n$ be checkered rectangle sized $n \times 4, n \ge 1$. Let $a_n$ be number of different $R_n$ tiling with rectangles sized $1 \times 3$. $\ \ \ $ $\ \ \ $ $\ \ \ $ $\ \ \ $ $\ \ \ $ $\ \ \ ...
5
votes
0answers
68 views

What is the maximal convex hull in $\mathbb R^3$ of a tree with fixed total length?

Denote by $\mathcal T_n$ the set of all trees on $n$ nodes. For a tree $T\in\mathcal T_n$, we assign to each edge a non-negative length such that the sum of all lengths is 1. Denote by $v(T)$ the ...
0
votes
0answers
107 views

The smallest disk containing all cirular arcs

In a comment to my recent question about covering segments by a disk, Gerhard Paseman has suggested a generalisation: replacing the segments of the original $n$-gon by a simple closed (say, convex) ...
6
votes
0answers
307 views

Smoothing a piecewise smooth manifold

Let $M \subset \mathbb{R}^d$ be a piecewise smooth $2$-manifold. Let $C$ be a polyhedral complex that covers $\mathbb{R}^d$ and contains faces of dimension $[0,d]$. Since $M$ is a $2$-manifold, we can ...
0
votes
0answers
23 views

Efficient sampling from a polytope with large number of contraints [duplicate]

As far as I know, the most popular way to sample from a polytope (in H-representation) \begin{equation} \mathcal{P} := \{z \in \mathbb{R}^n | (Az)_j \le b_j\; \forall j=1,2,\ldots,m\} \end{equation} ...
11
votes
1answer
171 views

Is there a proof of the uniformization theorem using circle packing?

In this paper: http://www.dm.unipi.it/~benedett/rodin-sullivan.pdf Rodin and Sullivan show that circle packings converge to the Riemann map. Later, Scharmm and He found another proof of the same ...
5
votes
1answer
131 views

Are the primary parallelotopes classified? (equivalently, Voronoi cells of lattices)

A primary parallelohedron is a polyhedron that can fill space with infinite translated copies. It is known (e.g., Coxeter, H. S. M. Regular Polytopes, 3rd ed. New York: Dover, pp. 29-30, 1973; or, ...
1
vote
0answers
42 views

Number of simplices contained in a convex body

I am interested in the following question: Given a convex body $K$ in $\mathbb{R}^d$ and an $\epsilon>0$ small enough, how many $d$-simplices $\{D_i\}_{i=1}^m\subset K$ do we need at least so that ...
0
votes
1answer
58 views

A bound on the Haussdorff distance

Let $X, Y \subset \mathbb{Z}^2$ be two discrete and bounded sets. Let $f_X$ be the Euclidean signed distance function of $X$ (similarly for $Y$) and $d_H(X,Y)$ the Euclidean Haussdorff distance ...
9
votes
3answers
257 views

Labeling edges of an icosahedron with sum constraints

The question is inspired by this previous MO question. There it was shown that it's possible to label the edges of a cube by the numbers $\{1,2,\ldots,6,8,9, \ldots, 13\}$ in such a way that: Three ...
3
votes
1answer
182 views

Status of Zeeman's collapsability Conjecture

Zeeman's conjecture in topological combinatorics states that if K is a contractible polyhedron of dimension 2, then K×I has a collapsible subdivision. What is the status of this conjecture ...
15
votes
5answers
587 views

The smallest disk containing all sides of an $n$-gon

Start with a regular $n$-gon of side 1 and consider its sides as open segments that can be moved around in the plane, allowing only translations. Two segments may not intersect. What is the ...
0
votes
0answers
60 views

Maximum value of linear function on the intersection of a parametrized family of balls

Let $C$ be a (nonempty) closed convex subset of $\mathbb{R}^n$ and $a, b \in \mathbb{R}^n$. Using the normal cone characterization of the euclidean projection operator $\mathrm{proj}_C$ (recall that ...
3
votes
1answer
100 views

How to show it is contained in a convex hull?

There are $(d+1)f$ points(denote set of all points as $S$) in $\mathbb{R}^d$, that can be divide into $d+1$ disjoint sets $F_1,...,F_{d+1}$, each set of size $f$. If we have $$ \mathcal{H}(F_i)\bigcap ...
19
votes
1answer
625 views

Covering of a surface of a cube $n\times n \times n$ by pieces of paper $1\times 6$

When I was too young one of my problems was in the list of problems of All-Russian Olympiad. The problem is the following: Problem. We have a surface of a cube $n\times n \times n$ such that each ...
1
vote
0answers
62 views

Affine-regular hexagon in convex body

An affine-regular $n$-gon is a non-degenerate affine image of the regular $n$-gon. It seems to be a standard fact in combinatorial geometry that inside every convex compact set $K\subseteq \mathbb ...
5
votes
1answer
155 views

Intersection of rotating regular polygons

This question has a recreational flavor, but may not be entirely uninteresting. Let $P_k$ be a unit-radius regular polygon of $k$ sides, and $P_n$ a unit-radius regular polygon of $n \ge k$ sides. ...
4
votes
0answers
78 views

Finding closest set of K disjoint hyperspheres to a point in $\mathbb{R}^n$ with uniform radius

I am interested in the following problem: in $\mathbb{R}^n$, we have $N$ overlapping hyperspheres all with the same radius. Given a point $p$ in $\mathbb{R}^n$, the objective is to find the $K$ non ...
6
votes
1answer
85 views

A question about simple closed plane polygons

For any positive integer $n$ greater than $3$, let $P(1),P(2),...,P(n)$ be a set of $n$ pairwise distinct points in the Euclidean plane, no three of which are collinear. Let $H(P(1),P(2),...,P(n))$ be ...
13
votes
0answers
229 views

Tiling a square with rectangles

Is it possible to completely tile a square with different rectangles of integer sides but all with the same area? The original problem, not requiring integer sides for rectangles, was proposed by Joe ...
5
votes
0answers
129 views

Is there a decomposition strengthening of the Sauer-Shelah Lemma?

Let $S \subset \{-1,1\}^n$. For a subset $A \subset [n]$ let $P_A$ denote the coordinate projection operator on S; in other words let $P_A(S)$ be the coordinate projection of $S$ onto the coordinates ...
14
votes
1answer
275 views

separating points in $\mathbb{R}^d$ by minimal number of planes

Given $n$ points of general position in $\mathbb{R}^d$ (say, $n>d$ and no $d+1$ lie in a hyperplane.) We want to draw $k$ hyperplanes not passing through those points so that they all are in ...
14
votes
1answer
297 views

Number of height-limited rational points on a circle

Consider origin-centered circles $C(r)$ of radius $r \le 1$. I am seeking to learn how many rational points might lie on $C(r)$, where each rational point coordinate has height $\le h$. For example, ...
7
votes
3answers
225 views

Embedding planar graphs into the grid

I've seen the following lemma in a paper. The result is by Valiant. A planar graph $G$ with maximum degree $4$ can be embedded in the plane using $O(|V|)$ area in such a way that its vertices are at ...