All Questions
2,368 questions
1
vote
0
answers
28
views
Integral hull of a polyhedron Q is polyhedron
Let $Q \subseteq R^n$ be a rational polyhedron and let $Q_I=Convexhull(Q \cap Z^n)$. By finite basis theorem, we have $Q=P+C$ for some rational polytope $P$ and finitely generated cone $C$ where $C=R_+...
- 21
1
vote
0
answers
66
views
To partition a triangle into $n$ convex pieces with sum of number of sides over all pieces maximized
This post is a variant on To cut a triangle into $n$ $p$-sided polygonal regions.
Question: Given a positive integer $n$, a triangular region is to be cut into $n$ convex pieces so that the sum over ...
- 5,979
-1
votes
0
answers
41
views
Is it possible to backtrack an optimization solver? [closed]
I have an optimization problem and was using a linear programming optimizer to find solutions. However, I find that past a certain size, the problem becomes "infeasible" and has no solutions....
10
votes
1
answer
156
views
For what $n$ do there exist non-periodic tilings with rotational symmetry of order $n$?
More precisely, given an integer $n$, does there exist a non-periodic tiling, where there are infinitely many patches within the tiling, of indefinitely large area, with rotational symmetry of order $...
- 263
2
votes
0
answers
85
views
On the trajectory followed by a point P on a planar convex region C when P is mapped repeatedly to the farthest point to it on C
Consider a planar convex region $C$. Let us define a mapping of a point $P$ on $C$ to that point on C that is farthest from $P$. Obviously, if from an initial position of $P$, we do this mapping ...
- 5,979
20
votes
1
answer
2k
views
Can you see through a cannonball packing?
More precisely, in a regular sphere packing, either the
HCP or FCC lattice packing,
does there exist a line $L$ disjoint from every sphere,
i.e., not touching any sphere?
If so, one could "look ...
- 151k
0
votes
0
answers
21
views
Easy instance of set cover
I am trying to prove that a natural greedy algorithm solves the following instance of the set cover problem: for a set of elements $e\in U$ with a set of weights $w_e$, we define the cost of a subset ...
- 4,049
3
votes
1
answer
103
views
References: rigorous algorithms for elementary computations in base-b with complexity estimates
Definitions/Notation: Fix positive integers $b$ and $M$. Consider the set of real numbers which can be exactly expressed with $2M+1$ coefficients in base $b$, defined by
$$\mathcal{X}(b,M):=\{x\in \...
- 5,405
1
vote
0
answers
56
views
Tiling with one of each 3D shape
Encouraged by the positive solutions to my question,
Tiling with one of each shape,
I'd like to pose the $\mathbb{R}^3$ equivalent:
Q. Is there a tiling of $\mathbb{R}^3$ by (bounded) polyhedra, one ...
- 151k
1
vote
1
answer
129
views
Packing problems where parts of objects are allowed to intersect
I'm interested in packing problems where the objects are allowed to intersect.
For a simple example, consider stacking 1×2 tiles on a nxn chessboard. Each 1×2 tiles consists of part X and Y (both 1×1)....
- 11
2
votes
1
answer
235
views
Tiling with one of each shape
Q. Is there a tiling of the plane by one each of simple polygons of $n$ vertices:
one triangle, one quadrilateral, one pentagon, $\ldots$ ,
one simple polygon of $n$ vertices, $\ldots$ ?
Here a ...
- 151k
9
votes
0
answers
143
views
Which polytopes have compact realization spaces?
Let $P\subset\Bbb R^d$ be a convex polytope.
Its reduced realization space is the space of all combinatorially equivalent polytopes modulo projective transformations.
I am interested in polytopes for ...
- 13.6k
7
votes
2
answers
242
views
Prove that $ n \leq d+1 $ under ordering constraints in $\mathbb{R}^d$
Let $x_1, \dotsc, x_n \in \mathbb{R}^d$ and $\theta_1, \dotsc, \theta_n \in \mathbb{R}^d$ be vectors such that for every $k \in [n]$, the following inequality holds:
$$
\langle x_k, \theta_k \rangle &...
2
votes
1
answer
108
views
Discrete isoperimetric inequality involving the diameter of an n-gon
I am interested in discrete isoperimetric-type inequalities that allow one to bound the perimeter of an $n$-gon from above (as opposed to below, as in the classical case when one bounds the perimeter ...
- 1,625
1
vote
1
answer
99
views
Is there any known upper bound for the local crossing number of a graph drawing in the plane?
The local crossing number ${\rm LCR(G)}$ of a graph $G$ is defined as the least nonnegative integer $k$ such that the graph has a $k$-planar drawing. In other words, it is the smallest possible number ...
- 1,190
1
vote
0
answers
97
views
How many non-overlapping, mutually non-antipodal unit spheres can be placed on the surface of four dimensional unit sphere?
If by linear or semi-definite programming this number could be shown to be less than 24, then this could be a route to showing that the 24-cell (consisting of 12 antipodal pairs of spheres) is the ...
- 11
1
vote
0
answers
118
views
'Uniformity' of surfaces of 3D convex solids
We try to go a little further from Which convex solids have geodesics on the surface that lie entirely in a plane?
Definitions: The surface of a finite 3D convex body may be called a convex surface. ...
- 5,979
1
vote
0
answers
51
views
Coarse-graining a hypergraph
$\DeclareMathOperator{\poly}{\mathrm{poly}}$I have asked this question on math.SE here, but couldn't get a satisfactory answer. I have also asked a related question on math overflow here, but haven't ...
- 277
2
votes
1
answer
93
views
Density of Intersection-Points of "Rational" Lines in the Euclidean Plane
consider the set of lines defined by all pairs of points $\lbrace[(u,v),(u-v,v+u)],\ u,v\in\mathbb{N}\rbrace$ in the euclidean plane
Question:
what is kown about the density of the set of ...
- 13.2k
-2
votes
1
answer
141
views
Solution to Erdos-Ulam problem [closed]
I have solved the Erdos-Ulam problem (see link) and can construct a set that satisfies the conditions (dense in R2 with all interpoint distances rational). I have expanded the solution from two ...
26
votes
0
answers
512
views
A non-self-intersecting unit side length polygon in a unit square has odd number of sides unless it is the square itself
This is the same question as here in SE.
I have a conjecture, it is like this:
Suppose there is a non-self-intersecting polygon lies inside a closed square of length $1$. The polygon has every side ...
- 843
1
vote
0
answers
72
views
Existence of a sequence of $-1/1$-polytopes with certain geometric properties
Let $P_n \subset \mathbb{R}^n$ be a sequence of polytopes (A polytope is the convex hull of finitely many points). Let $B_n \subset \mathbb{R}^{n}$ denote the Euclidean unit ball. I am interested in ...
- 93
4
votes
1
answer
285
views
The gacha stamp collector’s problem
Let $N \gg n \geq 2$ be fixed natural numbers. In the Gacha stamp game, players are given an $N \times N$ square grid, with each point occupied by a unique stamp.
On every turn, they may choose a ...
- 6,155
2
votes
4
answers
212
views
Efficient algorithm for graph problem
Let $D=(V,E)$ be a directed graph, $S,T\subset V$ and $f:V\rightarrow \{1,\ldots, k\}$ a positive, bounded weight-function and $l\in \mathbb{N}$, find a path $v_1,\ldots, v_l\in V$ with $v_1\in S$ and ...
- 157
4
votes
0
answers
90
views
Definition of Loop in an Oriented Matroid
I had posted this on Stackexchange because I don't believe this is a particlarly difficult question, but there were no answers, so I'm posting it on here now.
I just had a quick question about the ...
- 61
0
votes
0
answers
128
views
The smallest dihedral angle of convex polyhedrons
Given a set of points $\{x_{k}\}_{k=0}^{m} \subset \mathbb{R}^n$, is it always possible to find a constant $c=c(m,n)>0$, depending only on the dimension $n$ and the number $m$, such that, after ...
- 695
1
vote
0
answers
109
views
Which convex solids have geodesics on the surface that lie entirely in a plane?
We add a bit to On partitioning the surface of a convex solid into geodesically convex equal area regions
Consider a convex 3D solid body C - not necessarily a polyhedral body. What could be said ...
- 5,979
1
vote
1
answer
106
views
Iterated optimal transport
Suppose we are interested in two consecutive transport plans (in the Kantorovich formulation). That is, we are given finite sets $X$, $Y$ and $Z$, endowed with probability measures $\mu_X$, $\mu_Y$ ...
- 13
0
votes
0
answers
98
views
Number of tetrahedra inside a sphere with boundary A
I understand, that there are some combinatorial problems which are not yet solved regarding gluing triangulations in 3D. At least last time I checked, it was not yet known exactly how many ...
- 183
0
votes
0
answers
45
views
Functional inequalities on neighbourhood graphs
Consider an open domain $\Omega \in \mathbb{R}^d$, say the unit disk in $\mathbb{R}^2$ with $N$ points sampled i.i.d. on it. One of the simplest possible (unnormalised) discrete Laplacian of a ...
- 111
0
votes
0
answers
176
views
How to find a configuration of lines
In $\mathbb{R}^3$, can anyone help find a configuration of 5 lines such that the minimum of the smallest semi-axis lengths of the ellipsoid $ \mathbf{x}^T \mathbf{A} \mathbf{x} = 1 $, where $\mathbf{A}...
- 61
0
votes
0
answers
106
views
Upper bounds for minimum angle
What are the latest and best results on the asymptotic upper bound for the minimum angle between any pair of rays among $n$ rays in $\mathbb{R}^3$?
Any helpful answer would be appreciated. Thank you!
- 61
7
votes
0
answers
315
views
Sandwiching ellipses between planar convex bodies
Let $K$ and $L$ be planar convex bodies which are not ellipses. Does there exist an affine image $K'$ of $K$ such that
$K' \subset L$
No ellipse $E$ satisfies $K' \subset E \subset L$
I am also ...
- 4,653
1
vote
0
answers
58
views
On partitioning the surface of a convex solid into geodesically convex equal area regions
We refer to a subset S of the surface of a convex solid C as geodesically convex if the shortest path along the surface of C joining any two points in S lies entirely within S (and if there are more ...
- 5,979
4
votes
0
answers
66
views
Convergence of graph geodesics to geodesics on metric spaces
Let $(X,d)$ be a compact length space metric space $\mathbb{X}_{\delta}$ be a $\delta$-packing on $X$ and, for every $k\in \mathbb{N}_+$, let $G_{k,\delta}=(\mathbb{X}_{\delta},\mathcal{E}_k,W_k)$ ...
- 364
2
votes
1
answer
754
views
On a combinatorial inequality
Is it true that
\begin{gather}
\min\left(\lambda_{\min}(M_{12}), \lambda_{\min}(M_{13}), \lambda_{\min}(M_{14}), \lambda_{\min}(M_{15}), \lambda_{\min}(M_{23}), \\ \lambda_{\min}(M_{24}), \lambda_{\...
- 178
5
votes
1
answer
247
views
Question on the exact largest minimum angle
Could anyone help find the EXACT largest minimum angle between any pair of lines among 5 lines passing through the origin in $\mathbb{R}^3$? Additionally, what is the exact largest minimum angle ...
- 61
2
votes
1
answer
147
views
Are there polytopes with precisely two realizations?
A convex polytope is projectively unique if it has a unique realization up to projective transformations. Such polytopes are somewhat mysterious but still well-studied. Examples are simplices, the ...
- 13.6k
0
votes
1
answer
98
views
Chromatic tiling complexity and the chromatic number conjecture
Let $T$ be a finite set of tiles in $\mathbb{R}^d$. A tiling of $\mathbb{R}^d$ by $T$ is a collection of disjoint translates of tiles in $T$ whose union is $\mathbb{R}^d$. A tiling is $k$-chromatic if ...
7
votes
1
answer
242
views
Isoperimetric inequality, but $L_p$ norm
I would like to consider the isoperimetric problem of $L_p$ norm:
Given a region in $\mathbb R^2$ such that the boundary is a curve $C(x,y)$, where $\int_{C}(|\mathrm dx|^p+|\mathrm dy|^p)^{1/p}$ is a ...
- 843
8
votes
0
answers
149
views
Do the $\ell^{\infty}$ and $\ell^1$ norms yield minimal doubling constants amongst all norms on $\mathbb{R}^n$?
Setting:
Let $X:=\mathbb{R}^n$ for some positive integer $n$. For each $1\le p\le \infty$ let $d_p$ denote the metric induced by the $\ell^p_n$ norm thereon.
Note that, the doubling constant of a ...
- 5,405
3
votes
1
answer
237
views
Find the number of triangles in plane
Let $S$ be a set of $n$ points in the plane in general position. Each 3 points of S span a triangle. Total number of triangles spanned by S:
$$\binom{n}{3}=\frac{n(n-1)(n-2)}{6}=\frac{1}{6} n^3-O(n^2 )...
- 214
2
votes
1
answer
95
views
Dipping into sets of parallel edges in graph drawings
Given a multigraph embedded in the plane call a maximal set of parallel edges between $u,v$ such that only one of the induced faces contains nodes besides $u$ or $v$ a topologically parallel set (tell ...
- 111
4
votes
1
answer
356
views
Left and right halves of convex curve
Let $S$ be a set of $n$ points in the plane in general position (no 3 on a line), $n$ even.
A halving line is a line through $2$ points of $S$ that partitions $S$ into 2 equal parts ($(n-2)/2$ points ...
- 214
3
votes
1
answer
181
views
Probability measure on partition theorem
Probability measure in $\mathbb{R}^1$: Continuous function $f$ that is positive everywhere $\ \int_{-\infty}^{\infty} f dx =1$ (total area under the curve equals 1). For visualization see here.
...
- 53
3
votes
0
answers
110
views
How many Tverberg partition are in cloud of points? [closed]
Tverberg's Theorem: A collection of $(d+1)(r-1) +1$ points in $\mathbb{R}^d$ can always be partitioned into $r$ parts whose convex hulls intersect.
For example, $d=2$, $r=3$, 7 points:
Let $p_1, p_2,...
- 214
0
votes
0
answers
48
views
A question on a quantitative form of Farkas' lemma
Suppose A is an $m \times n$ matrix whose entries are non-negative integers and $\mathbf{b}$ is a vector with rational entries. A version of Farkas lemma implies that if the equation $$A\mathbf{x}=\...
- 6,214
2
votes
0
answers
318
views
What's the number of facets of a $d$-dimensional cyclic polytope?
A face of a convex polytope $P$ is defined as
$P$ itself, or
a subset of $P$ of the form $P\cap h$, where $h$ is a hyperplane such that $P$ is fully contained in one of the closed half-spaces ...
- 43
9
votes
1
answer
519
views
If we know the combinatorics of a polyhedron, and all but one of its dihedral angles, does that uniquely determine the remaining dihedral angle?
If we know the combinatorics of a polyhedron, and all but one of its dihedral angles, does that uniquely determine the remaining dihedral angle?
I’m happy to assume the polyhedron is simply connected, ...
- 2,896
5
votes
0
answers
82
views
What tools can show that (possibly irregular) dodecahedra do not fill space?
(Formerly on MSE.)
Here is a fairly natural question: Can three-dimensional space be filled with convex polyhedra of the same incidence structure (if not the same geometry) as the regular dodecahedron,...
- 3,068