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

learn more… | top users | synonyms (1)

-2
votes
0answers
32 views

On Incidence structure of finite Projective plane [on hold]

Consider a finite projective plane $\mathcal{P}$ over a finite field $F_q$, $q$ a prime power. Is it possible to define a map $f:\mathcal{P}\times \mathcal{P}\rightarrow \mathcal{P}$ such that (i) ...
14
votes
1answer
365 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
9 views
6
votes
1answer
174 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 ...
7
votes
1answer
192 views

Set of balls which the number of the ball intersects lines on the plane is bounded

Does there exist the set of balls(may be not disjoint) $X=\{B_i\subset\mathbb{R^2};i\in I\}$, satisfing following properties?(Note that the ball has a positive real radius) Let the set of all lines ...
2
votes
2answers
144 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 ...
3
votes
1answer
500 views

Tverberg partitions with less than (r-1)(d+1)+1 points

The Tverberg Theorem states the following: Let $x_1,x_2,\dots, x_m$ be points in $R^d$ with $m \ge (r-1)(d+1)+1$. Then there is a partition $S_1,S_2,\dots, S_r$ of $\{1,2,\dots,m\}$ such that $\cap ...
5
votes
2answers
641 views

On the joints problem in finite fields

The original version of the so-called "joints problem" consists of the following: Let $L$ be a set of lines in $\mathbb{R}^{3}$. Determine the maximum number of "joints" determined by these lines, ...
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 ...
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$ ...
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 ...
38
votes
3answers
3k views

Is the “Napkin conjecture” open? (origami)

The falsity of the following conjecture would be a nice counter-intuitive fact. Given a square sheet of perimeter $P$, when folding it along origami moves, you end up with some polygonal flat figure ...
3
votes
0answers
72 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? ...
22
votes
3answers
2k 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 ...
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
213 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. ...
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 ...
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$ ...
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, ...
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 ...
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)$$ ...
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 ...
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 ...
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 ...
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?
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 ...
7
votes
0answers
150 views

How big can a family of pairwise intesecting affine spaces be?

I apologize if this question might seem to be a bit too elementary. Let $\mathbb{P}^n$ be the projective space over $k$ - an algebraically closed field of characteristic 0. Let $1\leq l\leq n-1$, and ...
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 ...
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$. $\ \ \ $ $\ \ \ $ $\ \ \ $ $\ \ \ $ $\ \ \ $ $\ \ \ ...
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
193 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
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, ...
0
votes
1answer
159 views

Generalized Sphere Kissing Problem [duplicate]

I am currently researching discrete geometry and I am in need of an upper bound on a generalized kissing number in 3-dimensions dependent upon a parameter $\eta$ which is the radii of spheres touching ...
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) ...
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 ...
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 ...
15
votes
5answers
588 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 ...
5
votes
1answer
766 views

Linear transformation of a polyhedron

Is there a simple proof that shows: Linear transformation of a $\mathcal{H}$-polyhedron (i.e. the intersection of finitely many closed half-spaces) is a $\mathcal{H}$-polyhedron. Minkowski sum of ...
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 ...
11
votes
2answers
764 views

Fold-and-cut problem in three dimensions

The fold-and-cut theory states that "Any shape with straight sides can be cut from a single (idealized) sheet of paper by folding it flat and making a single straight complete cut. Such shapes include ...
20
votes
1answer
649 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 ...
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 ...