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

learn more… | top users | synonyms (1)

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 ...
6
votes
1answer
202 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
187 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
88 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
74 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
45 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
221 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
147 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
41 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
109 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
160 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 ...
1
vote
0answers
63 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 = ...
3
votes
2answers
84 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
70 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 ...
9
votes
1answer
269 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: ...
5
votes
1answer
193 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 ...
3
votes
1answer
131 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
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 ...
5
votes
2answers
99 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 ...
20
votes
0answers
315 views

Minimal number of intersections in a convex $n$-gon?

For a convex polygon $P$, draw all the diagonals of $P$ and consider the intersection points made by those diagonals. Let $f(n)$ be the minimal number of such intersections where $P$ ranges over all ...
2
votes
0answers
103 views

From Planar Graphs To Tangent Circles

I have a conjecture: "For each planar graph with vertices $V_1, V_2,\ldots, V_n$ there exist disjoint circles $w_1,w_2,\ldots,w_n$ in the plane, such that for every $i,j$, $w_i$ is tangent to $w_j$ ...
3
votes
1answer
129 views

Maximal $\pi/2$-separated subset of the sphere

A subset $A$ of a metric space is called $\varepsilon$-separated if $$dist(x,y)> \varepsilon \mbox{ for all } x\ne y\in A.$$ (Notice that the inequality in my definition is strict.) What is the ...
7
votes
1answer
420 views

Approximating a real by a ratio of primes

Let $x$ and $y$ be positive reals in $(0,1)$ with $x < y$ and $y-x =\epsilon$. I seek smallest primes $p$ and $q$ such that $$x \le \frac{p}{q} \le (x+\epsilon) = y \;.$$ Q. What upper bound ...
3
votes
1answer
100 views

The circle with minimal radius covering known finite set of points on a plane

Given some points on a plane, how to determine the circle with minimal radius covering all these points?
5
votes
0answers
117 views

Visibility in a prime orchard

This suggests a variant on Polya's orchard problem. That problem asks1 for which radius $\epsilon$ of trees at each lattice point within a distance $R$ of the origin block all lines of sight to the ...
5
votes
1answer
99 views

How to prove the existence of the polytope in $\mathbb{R}^d$ with a given number of faces, minimizing the isoperimetric ratio?

This is the isoperimetric type question. We know that in $\mathbb{R}^d$, balls are the sets that minimize the isoperimetric ratio $\frac{S^{d}}{V^{d-1}}$, where $S$ is the surface area and $V$ is the ...
2
votes
0answers
49 views

Algebraic independence in normed spaces

A set of $n$ points in $\mathbb{R}^2$ is algebraically independent over $\mathbb{Q}$ if there is no polynomial dependency among the $2n$ coordinates. A result (Lemma 3.3) from "Globally linked pairs ...
1
vote
1answer
210 views

Convex polyhedron and its Gauß-curvature [closed]

I have asked this question on MathSE and no one could give me an answer. So I'll post my question here. What I am trying to prove: A convex polyhedron has positive Gauß-Curvature at every vertex. ...
2
votes
0answers
98 views

need clarification of a paper by Fejes Toth

I would like some clarification about the following from Fejes Toth's paper "A stability criterion to the moment theorem" The setup is: For each positive integer $n$, let $r(H_n)$ and $R(H_n)$ ...
5
votes
1answer
156 views

Motzkin polynomials and enumeration of chord diagrams

On page 12 of the paper Enumeration of chord diagrams on many intervals and their non-orientable analogs" by Alexeev, Andersen, Penner, and Zograf is a list of polynomials which are a refinement of ...
7
votes
2answers
177 views

Special case of Erdos Distance Problem in a plane

Erdos in his Distinct distance Problem in a plane conjectured that the minimal number of distinct distance determined by $n$ points in a plane be $g(n)$, $$g(n) \sim \frac{cn}{\sqrt{\log n}}$$ But ...
7
votes
2answers
427 views

Embedding of planar graphs

I've recently come across the following lemma. Lemma (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 ...
3
votes
1answer
156 views

Number of lines of symmetry of a set of lattice points

Given some finite $S\subseteq\mathbb R^2$, it is clearly possible for $S$ to have arbitrarily many lines of symmetry. However, it is not very clear if the same is necessarily true for subsets of ...
4
votes
2answers
345 views

Geometry, Number Theory and Graph Theory of n-gon, permutation and graph labeling?

Given $n$ and $t$ lengths $ l_i, 1\leq l_1<l_2<\cdots<l_t\leq n-1$, of directed diagonals within an $n$-gon such that $l_1+\cdots+l_t\neq 0 \pmod n)$. Does it exist a directed path within ...
4
votes
1answer
136 views

Do random triangulation edge-flips maintain randomness?

Let $S$ be a fixed set of $n$ points in the plane in general position. Let $T$ be a triangulation of $S$, (somehow) selected uniformly at random from all triangulations of $S$. (There are an ...
3
votes
1answer
115 views

Maximal neighbour-full partition of $\{0,1\}^n$

What is the largest complete minor of the $n$-dimensional hypercube? (which we call $k(n)$) Alternatively, what is the partition of $\{0,1\}^n$ with each set connected and neighboring each other that ...
9
votes
4answers
285 views

Diameter of random segment intersection graph?

I have an even number of points $n$ randomly distributed (uniformly) in a disk. Then the points are randomly connected to form $n/2$ segments, a perfect matching. Finally, I form the intersection ...
11
votes
2answers
317 views

Double kissing problem

Consider two touching unit balls which will be called central balls. What is the maximum number $k$ of non-overlapping unit balls so that each ball touches as least one of two central balls? An easy ...
4
votes
1answer
124 views

Best polygonal approximation to a polynomial $\pm$ c

Let a planar region $R$ be defined by the vertical range bounded by a polynomial $f(x) \pm c$ with $c>0$ a constant, and with $x$ varying between the smallest and largest roots of $f(x)$. For ...
7
votes
5answers
341 views

Packing obtuse vectors in $\mathbb{R}^d$

I came across this attractive theorem: Theorem. In $\mathbb{R}^d$, there can be at most $d+1$ vectors that form an obtuse angle with one another. This was proved1 as a corollary of a lemma about ...
21
votes
7answers
1k views

What's that shape? Inferring a 3D shape from random shadows

Let $P$ be a bounded, simply connected region of $\mathbb{R}^3$. $P$ could be a polyhedron, or a smooth shape, or an arbitrary shape; I'll assume below that $P$ is a (non-degenerate, perhaps ...
6
votes
2answers
245 views

Existence of finite set of points in the revolving circles

Let $k$ and $n$ be two fixed integers. Let $C$ denotes the circle with radius $4n$ (in the plane $\mathbb{R}^2$). Suppose $\{C_1,C_2\}$ shows the set of two arbitrary tangent circles with radius $2n$ ...
1
vote
1answer
203 views

Ask the name of a combinatorial theorem

It is a classical theorem. For given integer $n \ge 1$, among ${n\choose{n/2}} = 2^{(1-o(1)n)}$ strings in the cube $\{0, 1\}^n$ with weights $n/2$, i.e., $n/2$ indices are 1, there are at least ...
11
votes
2answers
332 views

The most number of points that realize only $k$ distinct distances

For $k \ge 1$, let $f_d(k)$ be the largest possible number of points $p_i$ in $\mathbb{R}^d$ that determine at most $k$ distinct (Euclidean) distances, $\|p_i-p_j\|$. Example. For points in the plane ...
3
votes
2answers
171 views

Examples of toric threefolds

I am looking for examples of smooth projective toric threefolds $\mathbb P_\Delta$ such that the rational polytope $\Delta$ has only pentagonal faces and hexagonal faces. I quickly searched for ...
4
votes
2answers
73 views

Expressing a convex Polytope as a sublevel set of a function

Given an n-dimensional polytope $P$ in $\mathbb R^n$, Given as a convex hull of a finite set of points, $S$ I would like to construct an expliict formula for a function $f\colon \mathbb R^n \to ...
2
votes
0answers
144 views

Find the intersection between two convex hulls, in this specific case

We work over $\mathbb{R}^K$. Let $V$ be the set of vectors whose coordinates take values $0$ or $1$, or equivalently the corners of the unit cube $[0,1]^K$. Let $d:\{0, \ldots, K\} \to \mathbb{R}_+$ ...
2
votes
1answer
164 views

Epsilon-approximations of set systems with finite VC-dimension

ECorollary 6.9 in A Guide to NIP theories by Pierre Simon proves the following Theorem. For every positive integer $k$ and every positive real $\varepsilon$ there is an integer $n=n(k,\epsilon)$ ...
2
votes
2answers
232 views

Cardinality of non-integer points in the translation of the Minkowski sum of convex hull.

Let $\operatorname{conv}(a_1,\ldots,a_m)$ denote the convex hull of $\{a_1,\ldots,a_m\}$. Let $\mathbb{Z}_+=\mathbb{N}\cup\{0\}$ and $\mathbb{Q}_+$ denotes the positive (inluding 0) rational numbers. ...
5
votes
1answer
249 views

Looking for reference or proof to some facts stated on Anand Pillay's book

In my current work I am using facts 2.1.11 and 2.1.12 from Anand Pillay's book Geometric Stability Theory. The facts are stated as follows: Fact 2.1.11. Let $(S,\mbox{cl})$ be a locally ...