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

learn more… | top users | synonyms (1)

0
votes
0answers
23 views

Max number of points in a grid with distance to the origin between $d$ and $d+\sqrt{2}/2$, for some distance $d$? [closed]

Consider the square grid centered at the origin $\{-n,\ldots,n\}\times\{-n,...,n\}$. What is the value or an upper bound, as a function of $n$, of $\max f(d)$, where $d$ is the distance from some ...
3
votes
2answers
157 views

Existence of lattices whose circles have bounded number of points

For any plane lattice $\Lambda= \{ mA+nB: m,n \in \mathbb Z \}$, with $A,B$ linearly independent vectors in $\mathbb R^2$, we define the set of the circles in $\Lambda$ as $$\mathcal K(\Lambda) = \...
1
vote
1answer
111 views

Convergence of Discrete Geodesic

Let $M$ be a Riemmanian manifold, $p\in M$ and $V\in T_p(M)$. Suppose $f^{-1}:U_p \mapsto U$ is a diffeomorphism of a neighborhood of p to an open subset of $\mathbb{R}$ and define the sequence: \...
2
votes
1answer
85 views

Transformation inverting distances between two sets of diameter 1

Let $S_1, S_2 \subseteq \mathbb{R}^2$ be two finite disjoint sets of points in the plane with $\texttt{diam}(S_1) \leq 1$ and $\texttt{diam}(S_1) \leq 1$. Does there always exist a transformation $f: ...
0
votes
0answers
61 views

Number of polyhedra with N faces?

A. Up to isomorphism, how many polyhedra with N faces are there? Assume each face can be a triangle, square, pentagon, hexagon, etc... Furthermore each edge can be resized to any nonzero positive ...
8
votes
0answers
120 views

Computer searches for the $g$-conjecture

McMullen's $g$-conjecture aims the classify possible $f$-vectors of simplicial $d$-spheres. The $g$-conjecture has been proven for polytopal spheres and for simplicial spheres of dimension $d < 5$. ...
9
votes
2answers
473 views

Dissecting Ramanujan´s Cuboid: 1729 = 19 x 13 x 7

Consider the cuboid of dimensions 19 x 13 x 7 whose volume is 1729, the Hardy-Ramanujan number. What is the least number of smaller cuboids into which it can be dissected so that the resulting pieces ...
3
votes
0answers
44 views

Connectedness of semi algebraic set by c.a.d

I do not know whether there is a standard or some traditional ways to decide whether a semi algebraic set is connected or not. One way I know is c.a.d algorithm. I have read some papers of c.a.d ...
7
votes
2answers
207 views

Graphs with prescribed numbers of k-cliques

Let $(a_1,a_2,\dots, a_n)$ be a sequence of non-negative integers. Q. When does there exists a simple graph $G$ such that its number of $k$-cliques is $a_k$ (that is $G$ has $a_1$ vertices, $a_2$ ...
2
votes
1answer
90 views

How many distinct sets of n collinear points are there in an evenly-spaced two-dimensional grid of m x m points?

I'm seeking the definition of some function $f(n,m)$ which evaluates to the number of distinct sets of $n$ collinear points which are selected from an evenly-spaced two-dimensional grid of $m \times m$...
2
votes
1answer
133 views

How many lines of exactly n points can be placed in a discrete, square grid of size m x m?

Per the title, I'm seeking the definition of a function $f(n, m)$ which evaluates to the number of lines made from exactly $n$ points which can be placed on a two-dimensional discrete, square grid of ...
2
votes
0answers
46 views

lower bound for sum of (squared) distances under a minimum distance restriction

I am trying to solve a packing problem in discrete geometry and it would be useful to know the answer to the following problem. Let $A_1$, $A_2$,..., $A_n$ be $n$ points in the Euclidean plane $\...
0
votes
0answers
33 views

Experimental Investigations on the Statistics of Infinite, Discrete, Evenly Distributed Pointsets in the Euclidean Plane

I am trying to estimate the distribution of certain planar polygons in the Euclidean plane; to accomplish that, I generate finite set of points, that are evenly distributed in w.l.o.g. the $[0,1)\...
3
votes
2answers
107 views

Unit-Distance Polyhedra

What polyhedra are known to have two vertices adjacent if and only if they are of distance $d$ apart, for fixed $d$? For example, regular Platonic solids satisfy this condition, so I am looking for ...
14
votes
1answer
351 views

Banach-Mazur distance between the cube and the octahedron

The Banach-Mazur distance $d(X, Y)$ between two normed spaces $X, Y$ of the same dimension is defined as $d(X, Y) = \log\inf \|T\| \cdot \|T^{-1}\|$, where the $T:X \to Y$ is a linear and invertible ...
13
votes
2answers
585 views

Lattice n-gons with ordered side lengths 1,2,3,…,n

Consider the octagon in the Cartesian plane with vertices at (0,0), (1,0), (1,2), (4,2), (4,6), (7,2), (7,8), and (0,8). Are there other (infinitely many) polygons, such as this, lying entirely in ...
4
votes
0answers
55 views

Efficient CW structures on squarefree semi-algebraic set

General Setup Given a collection of $k$ polynomials (with real coefficients) in $n$ real variables, say $f_i(x_1,\ldots,x_n)$, let $V \subset \mathbb{R}^n$ correspond to those $x$-values for which ...
5
votes
1answer
127 views

Decidability of convex rearrangements of polygons

Triggered by the MO question, "How many convex shapes can be made with the pieces of the Stomachion?," I would like to pose this question: Q. Given $n$ polygons in a set $S$, say each with integer ...
7
votes
1answer
77 views

minimum number of bases of a matroid, that comes from a convex polytope

Given a d-dimensional polytope P with n points, then what is the minimum number of simplices that are spanned by vertices of P? This question led my research to matroids and so my question is: what is ...
3
votes
0answers
108 views

Zeros of Hilbert series of affine toric varieties

Consider a convex rational polyhedral cone $C\subset\mathbb R^m$ with vertex at the origin. Let $X$ be the corresponding affine toric variety, i.e. $\mathbb C[X]=\mathbb C[\mathbb Z^m\cap C^\circ]$. ...
4
votes
2answers
132 views

Classification of symmetries of tilings in surfaces?

Is there a general study of the symmetries of tilings on surfaces? Conway, Goodman-Strauss & Burgiel classified them on $\mathbb S^2, \mathbb R^2$ and $\mathbb H^2$, with their 'Magic Theorem'. ...
2
votes
0answers
53 views

What do you call the collection of all sets shattered by $F$?

The proof of Pajor's lemma uses the collection of all sets $S\subseteq X$ shattered by some $F\subseteq 2^X$. Is there a standard term for the former object? I've been privately referring to it as the ...
0
votes
0answers
36 views

Minimal subset of an $n$-dimensional grid intersecting every ($n$-dim) arithmetic progression of length $k$

Let $$A=\{1,2,...,l\}^n \subset \mathbb{R}^n$$ for some positive integers $l$ and $n$, and $B \subset A$ be a set such that $|B| \ll l^n$. I am interested in determining how small must $B$ be in ...
14
votes
0answers
154 views

Precise estimate for probability an $n$-point set has diameter smaller than $1$

This question was inspired by an earlier question that I answered but would like a more precise bound for. Consider random points $x_1, \dots, x_n$ in the unit ball in $\mathbb R^d$, uniformly and ...
2
votes
0answers
90 views

Balanced partitions of vector sets

We are interested in the following Lemma. Let $V\subset [0,1]^n\subset\mathbb R^n$ be a set of $n$-dimensional vectors. Then for each $r\le |V|$ there exists a partition $$V=V_1\cup V_2\cup\dots \cup ...
1
vote
1answer
72 views

Testing whether two vertices are neighbours

I face the following problem: I am given a high-dimensional, convex, bounded polyhedron in both vertex description: $X = \mathrm{conv} \, \{ v_1, \ldots, v_K \}$ and halfspace description: $X = \{ x \...
5
votes
2answers
145 views

Minimum length of a convex lattice polygon containing k lattice points?

Let $f(k)$ denote the minimum length of a convex lattice polygon containing exactly $k$ lattice points (including lattice points on the boundary). It is not too hard to show that $k = \frac{1}{4\pi} ...
12
votes
0answers
107 views

Rational inscribed realization of the regular dodecahedron

While it is clear that the regular dodecahedron $D$ cannot be realized with all integer coordinates, it is easy to find a polytope, which is combinatorially equivalent (face lattice isomorphic) to $D$ ...
9
votes
0answers
154 views

Determining convexity of a polygon from its Fourier coefficients

Consider an $n$-sided polygonal curve in the plane, represented by an ordered set of points $(x_0, x_1, \ldots, x_{n-1})$; line segments connect consecutive points and also $x_{n-1}$ to $x_0$. It is ...
2
votes
1answer
60 views

Constructing a polygon of $n$ facets from a set of positive values representing the length of the facets [closed]

The input of my problem is a set of positive values $a=\{a_1,...,a_n\}$ where $n\geq 3$. I want to construct an $n$-gon where the lengths of the $n$ facets are the values $a_i$ for $i=1,...,n$. My ...
12
votes
1answer
247 views

Covering the unit sphere by open hemispheres

Suppose $H_1,\ldots,H_{2n}$ are open hemispheres which cover $S^{n-1}$ with the property that removing any one of them leaves $S^{n-1}$ uncovered. Is it necessarily the case that the hemispheres can ...
8
votes
1answer
239 views

Integer sets with forbidden differences

Given a finite set $S$ of positive integers, and a positive integer $n$, let $F(n,S)$ be the largest possible cardinality of a subset of {$1,2,\dots,n$} no two of whose elements differ by a number in $...
1
vote
0answers
25 views

Homology of the subcomplexes of the “diamond shaped” sphere under 1-norm in $R^n$ as a simplicial complex

The 1-norm on $\mathbb{R}^n$ is defined by $\|v\| = |v_1| + |v_2| + \cdots + |v_n|$ for a vector $v = (v_1, \ldots, v_n) \in \mathbb R^n$. The unit sphere $S^{n-1}_1$ under the 1-norm is a simplicial ...
2
votes
2answers
163 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 ...
2
votes
0answers
89 views

Question on abstract polytopes

Let $(P,\le)$ be an abstract $n$-polytope, with $n\ge 2$. Let $H,H',K$ be $m$-faces, with $0\le m \le n-2$. Is it true that there is a sequence $\{H_0=H,H_1,\ldots,H_{r-1},H_r=H' \} \subseteq P$ so ...
4
votes
0answers
121 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$ (...
1
vote
0answers
37 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
89 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 ...
4
votes
0answers
164 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 ...
3
votes
0answers
108 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
50 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
80 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
67 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
223 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
54 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
53 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
120 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 ...
15
votes
1answer
662 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<\...
0
votes
0answers
18 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
88 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 ...