# Tagged Questions

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

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$? [on hold]

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 ...
157 views

72 views

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$ ...
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 ...
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 ...
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 ...
239 views

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 $... 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 ... 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 ... 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 ... 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$(... 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? ... 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 ... 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 ... 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 ... 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$... 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? ... 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 ... 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. ... 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 ... 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$... 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 ... 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<\...
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)$$ ...