All Questions
2,368 questions
0
votes
0
answers
36
views
ILPs with square constraint matrix
Given the Integer Linear Programming ($\text{ILP}$) problem
\begin{array}{ll}
\text{minimize} & c^T x \\
\text{subject to}& \mathbf{A}^T x \ge b \\
\text{where}&c,x,b\in\mathbb{N}_0^n,\\ &...
- 13.2k
2
votes
1
answer
101
views
Another lemma on intersections of $d$-simplices
Let $d\ge1$. A $d$-simplex $S$ is the convex hull in $\mathbb R^d$ of the vertices $v_0,\dots,v_d\in\mathbb R^d$ where $\{v_1-v_0,\dots,v_d-v_0\}$ is a linearly independent set of $d$ vectors; for ...
- 1,644
1
vote
0
answers
41
views
Are there rectangles that can be cut into non-right triangles that are pair-wise similar and pair-wise non-congruent?
We generalize the questions of Can a square be cut into non-right triangles that are mutually similar and pair-wise noncongruent?
Can any rectangle be cut into some finite number of triangles that ...
- 5,979
1
vote
0
answers
92
views
Can a square be cut into non-right triangles that are mutually similar and pair-wise noncongruent?
We add a bit to Tiling the plane with pair-wise non-congruent and mutually similar triangles and Cutting polygons into mutually similar and non-congruent pieces
A (non square) rectangle can obviously ...
- 5,979
2
votes
1
answer
88
views
A lemma on intersections of $d$-simplices
I have searched in vain for a combinatorial proof of Sperner's Lemma that rigorously proves the following:
Let $d\ge0$. A $d$-simplex is the convex hull in $\mathbb R^d$ of the vertices $v_0,\dots,...
- 1,644
0
votes
0
answers
26
views
Monotony of enforced subtour merging
Is it true that for a symmetric TSP instance in the sequence of edges generated by successively:
calculating the optimal 2-factor
adding cardinality constraints on the edgesets of the 2-factor's ...
- 13.2k
4
votes
0
answers
175
views
Can a square be partitioned into mutually non-congruent triangles all of same area and perimeter?
It is known that the plane cannot be tiled by pair-wise non-congruent triangles all having same area and same perimeter (https://arxiv.org/abs/1711.04504).
Question: Can a square be partitioned into ...
- 5,979
0
votes
0
answers
171
views
Solve NP-hard type problems with linear programming
I would like to know if there is any way to solve an NP-hard type problem, for example, the TSP, sum of subsets or knapsack problem, by using linear programming and not by brute force.
I ask this ...
1
vote
3
answers
273
views
A rational distance problem with (possibly) multiple solutions
Background: It is not known if any point exists on the XY plane that is at rational distance from all 4 vertices of a unit square lying on the XY plane (https://mathworld.wolfram.com/...
- 5,979
4
votes
0
answers
255
views
Economic equilibrium and tropical geometry
There is a famous saying in economics: When everyone pursues his or her own interests, there is an invisible hand that brings the market to equilibrium. However, this is not always the case. Here is ...
- 123
1
vote
0
answers
78
views
To tile the plane with mutually non-congruent rational triangles of equal area
We add a little to Tiling the plane with pairwise non-congruent rational triangles
Question: Can the plane be tiled by pair-wise non-congruent rational triangles all of which have same area? If "...
- 5,979
0
votes
0
answers
64
views
Alternatives to McCormick Envelope
I have an optimization problem for which I have the optimal solution obtained by the ILP.
However, when I introduced the McCormick Envelope to replace the product of a bi-linear term in its LP ...
- 3
2
votes
0
answers
119
views
Seeking insights on bounded set positive solutions for a set of linear systems in $\mathbb{R}^n$
Before delving into my query, I'd like to provide some context. Consider a continuous function $f:\mathbb{R}^{k}\rightarrow\mathbb{R}^{m}$ and a compact set $\mathcal{B}\subset \mathbb{R}^{k}$ (...
1
vote
0
answers
109
views
Which polygons allow partition into rational triangles?
A triangle with all side lengths rational is said to be a rational triangle. It is known - for example, Cutting the unit square into pieces with rational length sides - that the unit square allows ...
- 5,979
0
votes
1
answer
169
views
How to integrate an indicator function/constraint into the cost function of a linear program?
I have a mathematical model $P$ for which I optimize two cost functions say $F_1$ and $F_2$ subject to a set of constraints $C1$–$C10$.
In $F_2$, I want it to be included only when its expression ...
- 3
21
votes
1
answer
975
views
Conjecture: Given any five points, we can always draw a pair of non-intersecting circles whose diameter endpoints are four of those points
The following question resisted attacks at Math SE, so I thought I would try posting it here.
Is the following conjecture true or false:
Given any five coplanar points, we can always draw at least ...
- 3,507
41
votes
3
answers
2k
views
Is there a regular pentagon with a rational point on each edge?
This question was asked by Yaakov Baruch in the comments to the question Can a regular icosahedron contain a rational point on each face? It seems that this question deserves special attention.
- 12.3k
4
votes
0
answers
306
views
Regular solids and $\mathbb{Z}_5$
The mapping from the regular solids to $\mathbb{Z}_5$ given by the number of faces in the solid mod 5, interestingly, is a bijection. Any geometers or algebraists know if there is a significant ...
2
votes
1
answer
107
views
To find the convex planar region minimizing diameter when area and perimeter are given
The basic question is to find that planar convex region for which diameter is a minimum when area and perimeter are specified.
A partial answer is given here: http://nandacumar.blogspot.com/2012/11/...
- 5,979
0
votes
1
answer
126
views
On 'special' points on uniform planar convex regions defined in terms of moment of inertia
The following can be easily proved using perpendicular axes theorem and intermediate value theorem:
Lemma: Given any uniform planar convex region $C$ and any point on it, $P$, there will be at least ...
- 5,979
0
votes
0
answers
164
views
Inf-convolution of norm 1 and norm 2 square
The inf-convolution of the functions $f$ and $g$ defined on $\mathbb{R}^n$ is
$$
h(x)=\inf _{y \in \mathbb{R}^n} f(y)+g(x-y) .
$$
We can prove that if $f,g$ are convex functions, then $h$ is convex.
...
- 129
2
votes
0
answers
73
views
Is this an actual solution for centroidal Voronoi tiling, or just a visual approximation? [closed]
For the capstone project at the end of my graduate Data Science studies in late 2022, I needed an algorithm that would converge to something close to centroidal Voronoi tiling, while tiling contiguous ...
- 121
1
vote
0
answers
81
views
Embedding toric varieties in other toric varieties as a real algebraic hypersurface
In the question On a Hirzebruch surface, I've seen that the $n$-th Hirzebruch surface is isomorphic to a surface of bidegree $(n,1)$ in $\mathbb{P}^1\times \mathbb{P}^2$. I am trying to answer the ...
- 183
2
votes
1
answer
138
views
On the moment of inertia of planar convex regions and possible special nature of circular disks
We consider uniform convex planar regions and lines through their center of mass and lying in the same plane as the region; each line is parametrized by an angle $\alpha$ it makes with some reference ...
- 5,979
11
votes
1
answer
403
views
Smallest sphere containing three tetrahedra?
What is the smallest possible radius of a sphere which contains 3 identical plastic tetrahedra with side length 1?
- 111
6
votes
1
answer
253
views
Do lattices of small co-volume always exist in rational, connected, simply connected, nilpotent Lie groups?
Given a connected, simply connected, rational, nilpotent Lie group $G$, is there a lattice of arbitrarily small co-volume in $G$? If $G$ is Carnot, the answer is "yes" by applying a ...
- 243
2
votes
1
answer
136
views
On equal area planar sections of 3D convex bodies
This is an extension of On segments of equal area cut from planar convex regions by chords.
While the 3D analog of the above question would be about 3D pieces cut from a convex body $C$ by planes, ...
- 5,979
2
votes
1
answer
179
views
On segments of equal area cut from planar convex regions by chords
Consider a planar convex region $C$ of unit area and all chords of it that cut off a segment of area $\alpha$ from $C$. Obviously, if $C$ is a circular disk of unit area, all segments of area $\alpha$ ...
- 5,979
0
votes
1
answer
28
views
Calculating vertex potentials from optimal matchings
Question:
can the solution to the dual of a Linear Program be calculated directly from the solution of the primal Linear Program?
If yes, what are known algorithms and their bounds on complexity.
As ...
- 13.2k
2
votes
0
answers
81
views
Degeneracy and the "Linear Degeneracy Testing" problem
The Affine Degeneracy problem is about deciding whether $n$ given points in $\mathbb{R}^d$ (or $\mathbb{Q}^d$) are "in general position". i.e. there is no $d+1$ tuple of points which lies in ...
- 153
3
votes
0
answers
167
views
A formal inquiry of geometric-problem solving
Let $\Lambda$ be a finite set. Let $\mathcal{L}$ be a finite collection of lines on a plane $X$. Then, define $X^*(\mathcal{L}) = \bigcup_{L_\alpha\neq L_\beta} L_{\alpha}\cap L_{\beta}$ to be the ...
16
votes
0
answers
576
views
Snakes on a plane
A sleeping bag for a baby snake in $d$ dimensions (no, really) is a subset of $\mathbb{R}^d$ which can cover (via translation and rotation) every (piecewise-smooth for concreteness) curve of unit ...
- 21.2k
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 ...
1
vote
1
answer
63
views
Covering convex regions with disks optimizing on area and perimeter
Question: Are there planar convex regions $R$ and integers $n$ with the property: if $R$ is covered by $n$ disks of possibly different sizes such that (1) the total area of the covering disks is ...
- 5,979
2
votes
0
answers
84
views
Another variant of the Malfatti problem
We try to add to A Variant of the Malfatti Problem
As stated in the Wikipedia entry on Malfatti circles, it is an open problem to decide, given a number $n$ and any triangle, whether a greedy method ...
- 5,979
4
votes
2
answers
219
views
Algorithm for grouping tetrahedra from Voronoi diagram
I have a set of 3D Voronoi generator points and their neighbouring points, which, when connected, should result in a Delaunay tetrahedralization. However, I'm having a hard time implementing this. My ...
- 142
5
votes
0
answers
76
views
Is the choosability/list chromatic number of a circular arc graph equal to its chromatic number?
In 2003, Prowse and Woodall proved that for graphs $C_n^k$ which are powers of cycles,
$$\chi_\ell(C_n^k) = \chi(C_n^k).$$
They conjectured that this equality holds for the broader class of graphs ...
- 151
1
vote
0
answers
52
views
Does a substitution tiling being FLC depend on starting seed?
I've been trying to understand more on "geometric" substitutions rather than just symbolic ones. As symbolic substitutions always yield FLC tilings, I wanted to know whether a tiling coming ...
- 633
1
vote
0
answers
95
views
Detecting points inside the convex hull with inner products
Given a finite set $P$ of $n\gt d+1$ points in $d$-dimensional euclidean space.
Under the assumption that the points of $P$ are in general position in the sense that $\lbrace p_{i_1},\dots,p_{i_d}\...
- 13.2k
4
votes
1
answer
329
views
Billiard circuits in pentagons
A billiard circuit in a convex $n$-gon is a closed billiard path
of $n$ segments reflecting from consecutive edges of the polygon.
Every regular $n$-gon has such a billiard circuit:
Recently a ...
- 151k
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 ...
- 633
1
vote
0
answers
137
views
A comparison between packing and covering as classes of problems
We continue from Bounds for the Dispersal Problem in convex regions and Bounds for minimax facility location in a convex region
Let us consider the classes of problems:
Given a convex region $R$ and ...
- 5,979
0
votes
0
answers
63
views
Bounds for the Dispersal Problem in convex regions
We add a bit to: Bounds for minimax facility location in a convex region
Two earlier posts: Cutting convex regions into equal diameter and equal least width pieces - 2 and Facility location on ...
- 5,979
1
vote
0
answers
149
views
Ways of proving that a framework is locally rigid
Given a (bar-and-joint) framework/linkage, I would like to know what are possible ways of showing that the framework is locally rigid. Also, what is known about the computational complexity of ...
- 1,305
1
vote
0
answers
89
views
Bounds for minimax facility location in a convex region
An earlier question: Facility location on manifolds
A possibly related earlier post: Cutting convex regions into equal diameter and equal least width pieces - 2
The minimax facility location problem ...
- 5,979
3
votes
0
answers
226
views
Algorithm to dissect a polygon into a minimum amount of rectangles, conditioned on a maximum overlap
I have the following problem, I have a problem regarding concave polygons. I want to write code to cover any polygon with a minimum amount of rectangles that are allowed to overlap and have no fixed ...
- 31
8
votes
1
answer
442
views
When can $L$ sets of the form $\{a,b,a+b\}$ partition $\{1,2,\dots, 3L\}$?
Firstly, this question has been posted to Math StackExchange with no complete answer so far.
Consider a set of the form $\{a,b,a+b\}$ where $a$ and $b$ are positive integers with $b > a$. I will ...
2
votes
2
answers
679
views
Sphere tessellation with congruent regular hexagons except finitely many
Let $S^2$ be the 2 dimensional sphere embedded in $\mathbb{R}^3$. It is well known, using the Euler characteristic, that it is not possible to tessellate $S^2$ with all congruent regular hexagons.
My ...
- 131
25
votes
1
answer
513
views
Is there an inventory of closed billiard paths in a regular tetrahedron?
Conway found a closed billiard-ball trajectory in a regular tetrahedron:
Image: Izidor Hafner
Since then Bedaride and Rao
Bedaride, Nicolas, and Michael Rao. "Regular simplices and periodic ...
- 151k
12
votes
0
answers
168
views
Can the optimal packing density in $\mathbb{Z}^d$ be irrational?
For a finite $S \subset \mathbb{Z}^d$, let $d_p(S)$ be its optimal packing density. That is, the maximal lower asymptotic density of $A+S$, where $A \subset \mathbb{Z}^d$ is such that $(a_1+S)\cap (...
- 1,209