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

learn more… | top users | synonyms (1)

10
votes
1answer
230 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
117 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
54 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
21 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
56 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
201 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
277 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 $g^...
3
votes
1answer
277 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
76 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 ...
1
vote
0answers
111 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
26 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
191 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
137 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
46 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
279 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
193 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
604 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
65 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
147 views

How many points are in such set with the same norm-2

Let $L=[a,b]\cap\mathbb{N}$ with $a,b\in\mathbb{N}$, let $D\in\mathbb{N}$, and let $C=L^D$. Then I would like to know how many points are there in $C$ with the same given norm-2 $d$. I.e., I'm looking ...
3
votes
1answer
125 views

How to show it is contained in a convex hull?

There are $(d+1)f$ points (denote the 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)\...
20
votes
1answer
742 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
71 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 R^2$...
5
votes
1answer
162 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
82 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
92 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 ...
25
votes
0answers
526 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
143 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 ...
15
votes
1answer
292 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
299 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
244 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 ...
6
votes
1answer
261 views

Lattice points on the boundary of an ellipse

How many points of the integer lattice ${\mathbb Z}^2$ can an axis-parallel ellipse of radius $r$ contain on its boundary? (that is, we consider ${\mathbb Z}^2$ as lying in ${\mathbb R}^2$). ...
6
votes
1answer
215 views

What's the difference between a PL simplicial sphere and a shellable simplicial sphere?

Shellability of a simplicial sphere tells us that we can build up the complex one facet at a time such that at each step (except the last step) the complex is a PL-ball. At the last step it is of ...
6
votes
1answer
94 views

Above/below directed graph on cells of arrangement of lines

This question concerns the structure of a directed graph built on the cells of an arrangement of lines. My basic question is whether this graph has been studied before, perhaps in another guise. I ...
2
votes
1answer
77 views

distinct multiple points in a space with at least one point lying in a subspace

Let $X$ be a topological space and $A$ a subspace of $X$. Given $k\geq 2$, let the unordered configuration space be $$ B(X,k)=\{(x_1,x_2,\cdots,x_k)\in X^k\mid x_i\neq x_j \text{ for any } i\neq j\} $$...
0
votes
0answers
48 views

Finding spanning vector sets

Let $V$ be the set of all vectors over the non-negative integers. For any two subsets $S$ and $T$ of $V$, define $S + T$ to include: All vectors in $S$ All vectors in $T$ All vectors that can be ...
1
vote
0answers
235 views

Reduction to some physical interpretation of this formula

Problem Given N 3-dimensional points which are {$p_1,p_2,..,p_n$} where $p_i = (x_i,y_i,z_i) $ . I have to find the value of the formula $$ \sum \limits_{i=0}^n \sum \limits_{j=i+1}^n \frac{ \mid \...
7
votes
0answers
149 views

Which -icial sets produce the “standard” representations of symmetric groups?

Suppose you have a system of cell complexes (say, even convex polyhedra) $(P_n)_{n\geqslant0}$ which occur as faces of each other and are used to define the corresponding notion of "$P_*$-set". So ...
4
votes
0answers
48 views

How does one go from convexity to submodularity?

If I have a function which is convex in the hypercube, $[-1,1]^n$ then when would it imply that its restriction to $\{-1,1\}^n$ is submodular? It would be helpful is someone can share some specific ...
9
votes
2answers
115 views

Generate polyhedra by collapsing vertices of a polyhedron

I am looking for basic information about the following idea: (I) Consider a square. By collapsing two adjacent vertices, we obtain a triangle. (II) Consider a three-dimensional cube. By collapsing a ...
6
votes
3answers
184 views

Probability of random geodesics on the half-sphere intersecting

4 end points (a,b,c,d say) are chosen uniformly randomly and connected a to b and c to d by two geodesics on the 2-dim half-sphere. Here, uniform means that, probability that a point lies on a surface ...
2
votes
1answer
116 views

Choosing the weights of a Voronoi diagram — is this function always the gradient of another function?

This question is related to the earlier question Weighted area of a Voronoi cell . As in that question, let $X = \{ x_1,\dots,x_n\} $ denote a set of $n$ points in the unit square $S = [0,1]\times[0,...
3
votes
2answers
90 views

Basic question about discrete minimal surfaces

Let $P$ be a convex polygon with $n > 3$ vertices $v_1, \ldots, v_n \in \mathbb{R}^2$, let $x$ be a point in the interior of $P$, and let $u$ be a function with prescribed values at the vertices of ...
5
votes
0answers
86 views

Algorithm to express a point from a H-polyhedron as convex combination of extreme points

Let $P\subset\mathbb{R}^n$ be a convex polyhedron described as an intersection of hyperspaces, that is, $$P:=\{\boldsymbol{x}: A\boldsymbol{x} \leq \boldsymbol{b}\}$$ Let $\boldsymbol{x} \in P$. We ...
10
votes
1answer
296 views

What can we learn from the newly discovered monohedral convex pentagonal tiling?

Wikipedia: https://en.wikipedia.org/wiki/Pentagonal_tiling#Stein_.281985.29_and_Mann.2FMcLoud.2FVon_Derau_.282015.29 Media coverage: http://www.theguardian.com/science/alexs-adventures-in-numberland/...
9
votes
4answers
624 views

Is this an instance of any existing convex pentagonal tilings?

Inspired by Wikipedia's article on pentagonal tiling, I made my own attempt. I believe this belongs to the 4-tile lattice category, because it's composed of pentagons pointing towards 4 different ...
5
votes
1answer
196 views

Smoothening a measure, II

There is an almost invisible, but significant difference between the question below and that recently answered by Boris Bukh. Given a probability measure $\mu$ supported on a finite set $S\subset{\...
3
votes
1answer
134 views

Smoothening a probability measure

Given a probability measure $\mu$ supported on a finite set $S\subset{\mathbb R}^2$, define $$ f(z):=\max\left\{\frac{\mu(x)+\mu(y)}2\colon \frac{x+y}2=z,\ x,y\in S \right\}, \ z\in{\mathbb ...
7
votes
1answer
258 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 ...
5
votes
2answers
101 views

Inscribed parallelotope in a $d$-simplex

The problem setup is simple: Given a $d$-simplex $\Delta_d:=\{(x_1,\cdots,x_d):x_i\geq 0,\sum_i x_i\leq 1\}$, can we construct a finite sequence of parallelotope $A_i$ so that $\Delta_d=\cup_{i=1}^N ...