All Questions
2,368 questions
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
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
2
votes
1
answer
202
views
To cut a triangle into $n$ $p$-sided polygonal regions
Given any triangular region and two integers $n$ and $p$ which can be large and $p > 4$. It is needed to cut the triangle into $n$ $p$-gons (e.g., cut a triangle into 10 heptagons). Among the $p$-...
- 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....
14
votes
5
answers
1k
views
Emergence of the discrete from the continuum
An almost eternal theme in Mathematics is the approximation of the Continuum by the Discrete. This core idea goes back at least to Archimedes, and remains active to these very days (and quite likely ...
- 12.7k
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 $...
- 6,652
2
votes
1
answer
874
views
Interpreting mincost flow dual variables
Consider the task of finding flow of size $b$ with minimum possible cost.
It may be formulated as linear programming in a following way:
$$\boxed{\begin{gather}
\min\limits_{f_{ij} \in \mathbb R} &...
CommunityBot
- 1
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
10
votes
1
answer
673
views
A random variation on Pólya's orchard problem
Pólya's orchard problem is as follows:
"How thick must the
trunks of the trees in a regularly spaced circular orchard grow if they are
to block completely the view from the center?"
See, e....
- 105k
0
votes
1
answer
187
views
Matching bins up to shuffling II
Suppose a school purchases a set $\mathcal{S}$ of balls, say
$$\displaystyle \mathcal{S} = \{b_1, b_2, \cdots, b_n\}$$
with $n$ very large. The balls $b_j$ are pairwise distinct and have distinct ...
CommunityBot
- 1
0
votes
2
answers
530
views
Any idea of solving an optimization problem with cubic constraints?
I have the following optimization problem with cubic constraints, which is hard to solve. Are there any ideas, or related references, of solving such a problem?
$$ \begin{array}{ll} \underset {y, z} {\...
CommunityBot
- 1
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 ...
- 3,068
11
votes
1
answer
651
views
How to correctly state Cauchy's rigidity theorem?
Cauchy's rigidity theorem is often stated briefly as
Any two (convex, 3-dimensional) polyhedra with pairwise congruent faces are themselves congruent.
As a more formal generalization to general ...
- 13.6k
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 \...
- 63.9k
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
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
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 ...
- 976
1
vote
1
answer
227
views
On comparing planar convex regions of equal perimeter and area
Definitions:
The Hausdorff distance between two point sets is the greatest of all the distances from a point in one set to the closest point in the other set.
Given two planar convex regions $C_1$ ...
CommunityBot
- 1
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 &...
- 109k
1
vote
1
answer
234
views
Positioning a member of an interval partition
Let $\ 0<\Lambda_1\le\ldots\le\Lambda_n\ $ be a finite non-decreasing sequence of positive reals, of length $\ n>0.\ $ Let
$$ D:=\sum_{k=1}^n \Lambda_k $$
The question is about the conditions ...
CommunityBot
- 1
1
vote
1
answer
178
views
Inside-out dissections of solids -2
We record some general questions based on
Inside-out dissections of solids
Inside-out dissections of a cube
Can every convex polyhedral solid be inside-out dissected to a congruent polyhedral solid?...
- 5,979
10
votes
3
answers
460
views
Do triple-linked graphs exist?
Lets say that a finite simple graph $G$ is (intrinsically) fully triple-linked if for each embedding of $G$ into $\Bbb R^3$ we can find three disjoint cycles $C_1,C_2,C_3\subset G$ whose embeddings ...
- 13.6k
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 ...
- 21
9
votes
3
answers
563
views
Visual proof of convergence for Steiner's symmetrization
I want to find a visual proof of the following fact:
For any convex figure in the plane there is a sequence of Steiner's symmetrizations that makes it arbitrary close to a circular disc.
All ...
- 2,222
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
3
votes
1
answer
210
views
Exponential growth of shortest vector norm for successive lattices corresponding to powers of a matrix
Let $A\in M_{2\times 2}(\mathbb{Z}) $ be a two by two integer matrix such that $0,\pm 1$ are not eigenvalues of $A$ and $\left|\det(A)\right|>1$. I am interested in the growth of the norm shortest ...
CommunityBot
- 1
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
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
6
votes
1
answer
413
views
How many unit cubes are needed to 'hide' a unit cube fully in 3D?
Question: What is the smallest number of nonoverlapping unit cubes that can hide a unit cube C - in the sense that every ray emanating from the boundary of C meets the interior or the boundary of one ...
- 506
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
7
votes
1
answer
117
views
Packing points in a lattice
Let $L$ be the square or triangular lattice in the plane, with nearest neighbors having distance 1. Has anyone studied the problem of finding the maximum (okay, supremum) density achieved by a subset ...
- 506
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
3
votes
1
answer
855
views
Infinite dimensional lattice for integers and the Riemann hypothesis?
It is known that for each finite set of primes $p$ we have: $\log(p)$ are linear independent over the rational numbers.
We have $\log(ab) = \log(a)+\log(b)$ and $\log(n) = \sum_{p |n}v_p(n) \log(p)$.
...
CommunityBot
- 1
2
votes
1
answer
137
views
Reconstructing a matroid by its minors
Proposition 3.1.27 in Oxley's Matroid Theory says that given a matroid $M$ and an element $e\in E(M)$ such that $e$ is not a loop or a coloop, the pair $(M/e, M\setminus e)$ uniquely determines $M$. ...
- 500
1
vote
1
answer
138
views
Recognizability/unique composition property for substitution tiling
This may be a very basic question, but I have not found an answer to it so far in my search. The question is whether there is an "algorithmic" way to check unique-composition/recognizability ...
CommunityBot
- 1
-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 ...
- 3,068
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 ...
- 148k
2
votes
2
answers
226
views
On cutting tetrahedrons into mutually congruent pieces
Simple observations: A regular tetrahedron can be cut into 2 mutually congruent pieces (in 3 obvious ways which are all basically the same way, giving one and same pair of congruent pieces). The ...
- 6,101
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
1
vote
1
answer
115
views
$\mathrm{LP}$ formulation for $\mathrm{k}$-$\operatorname{opt}$ moves
$\mathrm{k}$-$\operatorname{opt}$ moves are an idea to improve non-optimal Hamilton cycles in weighted symmetric graphs by exchanging $\mathrm{k}$ tour-edges with $\mathrm{k}$ edges that do not belong ...
CommunityBot
- 1
10
votes
2
answers
254
views
Is the face lattice of the cube a polytope graph?
The face lattice of a
convex polytope $P\subset\Bbb R^d$ is the partially ordered set whose elements are the faces of $P$ ordered by inclusion. We can turn it into a graph by considering its Hasse ...
- 13.6k
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 ...
- 63.9k
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
13
votes
0
answers
378
views
Is a convex polyhedron determined by its edge lengths and angular defects?
Let's consider 3-dimensional convex polyhedra $P\subset\Bbb R^3$.
The angular defect at a vertex $v$ is $2\pi$ minus the sum of the interior angles of the incident faces at $v$.
Question:
Is a ...
- 13.6k
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$ ...
- 128k