All Questions
1,020 questions
10
votes
3
answers
2k
views
Is there an absolute geometry that underlies spherical, Euclidean and hyperbolic geometry?
A space form is defined as a complete Riemannian manifold with constant sectional curvature. Fixing the curvature to +1, 0 & -1 and then taking the universal cover by the Killing–Hopf theorem ...
- 2,369
1
vote
0
answers
47
views
Characterization of Gaussian Gram matrices
From Euclidean geometry we know that a matrix $C$ is a matrix of squared Euclidean distances between some points if and only if $-\frac{1}{2} H D H \succeq 0$ (positive semi-definite) with $H = (I - \...
- 407
12
votes
2
answers
1k
views
Group generated by two irrational plane rotations
What groups can arise as being generated by two rotations in $\mathbb R^2$ by angles $\not \in \mathbb Q\pi$?
If the centers of the rotations coincide, then the rotations commute and generate some ...
- 1,277
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
383
views
Geometry in $\mathbb{R}^n$: angle between projections of a rectangle
Consider a hyper rectangle $R$ in $\mathbb{R}^n$ defined by $|x_i|\leq M_i$ for all $i\leq n$.
Consider a linear affine subspace $L$ of dimension $1\leq k <n$ such that $L\cap R\neq \emptyset$.
For ...
- 21
2
votes
1
answer
186
views
An alternative to Cayley Menger determinant for calculating simplex volume
I recently came across the determinant of a symmetric $3\times 3$ matrix
$\begin{pmatrix}
2a^2& a^2+b^2-c^2& a^2+d^2-e^2\\
a^2+b^2-c^2& 2b^2& b^2+d^2-f^2\\
a^2+d^2-...
- 13.2k
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
35
votes
4
answers
3k
views
Psychological test for Euclidean geometry [closed]
There is the so-called FCI test. It contains a list of questions such that anyone who can speak will have an opinion. Based on the answers one can determine if the answerer knows elementary mechanics. ...
- 45k
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 ...
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}$ (...
0
votes
0
answers
32
views
Enumeration of flat integral $K_4$
Question:
What is known about the enumeration of all $(a,b,c,d,e,f)\in\mathbb{N}^6_+: \\ \quad\operatorname{GCD}(a,b,c,d,e,f)=1\ \\ \land\ \exists \lbrace x_1,x_2,x_3,x_4\rbrace\subset\mathbb{E}^2:\ \...
- 13.2k
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
1
vote
1
answer
253
views
"On models of elementary elliptic geometry"
While perusing p. 237 of the 3rd ed. of Marvin Greenberg's book on Euclidean and non-Euclidean geometries, I learned that it can actually be proven that "all possible models of hyperbolic ...
- 8,842
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
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
2
answers
241
views
Does "perpendicular phase incoherence" satisfy the triangle inequality?
I asked this question at https://math.stackexchange.com/q/4783968/222867, but even after a 200-point bounty, no solution was provided, only some thoughts regarding possible directions. So I'm now ...
- 698
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
17
votes
3
answers
2k
views
Is symmetric power of a manifold a manifold?
A Hausdorff, second-countable space $M$ is called a topological manifold if $M$ is locally Euclidean. Let $SP^n(M): = \left(M \times M \times \cdots \times M \right)/ \Sigma_m$, where product is done $...
- 506
4
votes
3
answers
1k
views
Is there a pyramid with all four faces being right triangles? [closed]
If such a pyramid exists, could someone provide the coordinates of its vertices?
1
vote
0
answers
94
views
Linear Program Optimal Value
If $f(A,b,c)$ is the optimal value of a linear program
$\min c.x$
subject to $A.x \leq b ; x \geq 0.$
Does $f(A,b,c)$ have a piecewise polynomial/rational upper bound in $(A,b,c)$ on the domain of ...
0
votes
1
answer
114
views
Mixed integer program and continuous Diophantine approximation
Let $n\in\mathbb{N}$ such that $n\geq 2$ and let $0<r<1$ be a real number. We wish to solve the following problem.
$$\min_{(t,(z_j)_{j=2}^n) \in \mathbb{R}\times \mathbb{Z}^{n-1}} t$$
subject to ...
3
votes
1
answer
212
views
Another implication of the Affine Desargues Axiom
Definition 1. An affine plane is a pair $(X,\mathcal L)$ consisting of a set $X$ and a family $\mathcal L$ of subsets of $X$ called lines which satisfy the following axioms:
Any distinct points $x,y\...
- 41.8k
2
votes
1
answer
240
views
Is the problem of vertex enumeration from an H-representation of a polytope NP-hard?
According to the Wikipedia page on the issue, the vertex enumeration problem is NP-hard.
However, double description and reverse linear search are algorithms listed to solve the problem. Moreover, ...
- 123
10
votes
1
answer
522
views
A projective plane in the Euclidean plane
Problem. Is there a subset $X$ in the Euclidean plane such that $X$ is not contained in a line and for any points $a,b,c,d\in X$ with $a\ne b$ and $c\ne d$, the intersection $X\cap\overline{ab}$ is ...
- 41.8k
0
votes
0
answers
55
views
Relationship of optimal solutions between the total function and the sub function
This is an unconstrained convex optimization problem. Let $\mathcal{N}=\left\{1,\ldots,n\right\}$, $2\leq n<\infty$. Suppose there are many strongly convex functions $f_i(x)$, where $x\in\mathbb{R}^...
- 1
0
votes
0
answers
85
views
Show that $\max_{P_X : X\in (0,1) } \left| \frac{\mathbb{E} [ f'(X) ]}{ \mathbb{E} [ f(X) ] } \right|$ is maximized by at most two mass points
Let $f$ be some given well-behaved function. Consider the following optimization problem overall probability distribution on $[0,1]$
\begin{align}
\max_{P_X : X\in [0,1] } \left| \frac{\mathbb{E} [ ...
- 671
1
vote
1
answer
69
views
$A^*$ algorithm to find shortest path when weights in my graph are the inverse of distance
Given a graph G=(V,E) where the weights on my edges are inverse of Euclidian distance between nodes, I want to know if I can use A* algorithm to find the shortest path. How I need to modify the ...
- 111
6
votes
1
answer
374
views
Desargues ten point configuration $D_{10}$ in LaTeX
I want to draw the Desargues configuration $10_3$ in LaTeX using the standard picture environment, which allows only lines with the slopes $n:m$ where $\max\{|n|,|m|\}\le 6$. Is it possible? If not, ...
- 41.8k
1
vote
0
answers
23
views
Estimate on the minimum distance from integer points on some fixed hyperplanes to a moving hyperplane
Suppose in $\mathbf{R}^n$ there are $m$ given hyperplanes $\Pi_j:\sum_{i=1}^n c_{i,j}e_i=0$ all of which go through the origin, and all the coefficients $c_{i,j}$ are rational (you can make them all ...
- 909
0
votes
0
answers
92
views
Finding a point that minimizes sum of distances to a given set of lines
Given a set $L$ of size $n$ of lines in $\mathbb{R}^d$, find a point $x \in \mathbb{R}^d$ that minimizes: $$\sum\limits_{l\in L}\min\limits_{y\in l} {\lvert \lvert x-y \rvert\rvert}^2$$
I wrote a 1.5-...
- 19
1
vote
1
answer
119
views
Optimization on non-convex set
Let $\Omega$ be an open bounded subset of $\mathbb{R}^2$ and $f\in L^2(\Omega)$ be a given function. Consider the optimization problem
$$\mathrm{min} \int_\Omega u(x) f(x) \,dx\,,$$
where a minimum is ...
- 11
11
votes
3
answers
557
views
Was the small Desargues Theorem known to ancient Greeks?
My question concerns the classical Desargues Theorem and its simplest version
The small Desargues Theorem: Let $A$, $B$, $C$ be three distinct parallel lines and $a,a'\in A$, $b,b'\in B$, $c,c'\in C$,...
- 41.8k
2
votes
1
answer
91
views
Calculating a relaxed Delaunay Triangulation
The triangles of a planar Delaunay Triangulations are essentially characterized by the property that no triangle's corner is inside another triangle's circumcircle; Delaunay Triangulations can be ...
- 13.2k
1
vote
1
answer
96
views
Is every triangulation the projection of a convex hull
Question:
given the triangulation $T$ of a set $P$ of $n$ points $p_1,\dots,p_n$ in the euclidean plane whose convex hull is a triangle, can we always find a set $Q$ of $n+1$ points $q_0,q_1,\dots,q_n$...
- 13.2k
2
votes
0
answers
213
views
A generalization of the Archimedean circle
I proposed a generalization of the Archimedean circle : In this figure $M$ is the midpoint of $AB$, $DE$; $(G)$, $(H)$, $(M)$ are the semicircles. Then two yellow circles are congruent.
Question: Is ...
- 1,776
3
votes
0
answers
220
views
Which manhole covers fall through their holes?
Apparently one of the reasons why all manhole covers are shaped like discs is because for any other shape, the manhole cover would fall through its own hole. As stated this is not necessarily a ...
- 26.9k
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} {\...
- 21
6
votes
1
answer
167
views
$\mathbb{Q}$-rank of the space of angles of pythagorean triples
A pythagorean triple is a triple of integers $(a,b,c)$ with $a^2 + b^2 = c^2$. Given a triple, $(a/c, b/c)$ is a point on the unit circle, so we may associate to it the normalized angle
$$\theta_{a,b} ...
- 7,527
1
vote
2
answers
121
views
How to solve the optimization problem $\max_{\mathbf{w}}\sum_i\text{sign}(\mathbf{w}^T \mathbf{x}_i)$?
I am looking for an algorithm to solve the following optimization problem
$$\max_{\mathbf{w}}\sum_i\text{sign}(\mathbf{w}^T \mathbf{x}_i)$$
where $\mathbf{w}$ and each $\mathbf{x}_i\in\mathbb{R}^d$.
...
- 175
6
votes
1
answer
435
views
On the aperiodic monotile
One of the more mind-boggling aspects of the Penrose tiles is that there are uncountably many distinct tilings of the plane, but every tiling contains every finite region that appears in another ...
- 4,898
0
votes
0
answers
128
views
Concurrencies determined by intersections of angle trisectors (and isogonal lines) in a triangle
The famous Morley’s theorem, states that in a triangle the interior angle trisectors, proximal to sides respectively, meet at the vertices of an equilateral. However the six trisectors meet at 12 ...
22
votes
1
answer
1k
views
Aperiodic monotile without reflections?
The recently discovered amazing aperiodic monotile (or "einstein") of David Smith, Joseph Samuel Myers, Craig S. Kaplan, and Chaim Goodman-Strauss tiles the plane only if reflections of the ...
- 82.6k
3
votes
0
answers
105
views
Techniques for solving linear inequalities
For $n$ real variables $x_1, \ldots, x_n$, I have a bunch of inequalities of form $2 x_i > x_j + x_k$ or $2 x_i < x_j + x_k$, where $i,j,k$ are distinct. My goal is to determine whether this set ...
- 231
0
votes
0
answers
79
views
Geometry of inner products between the unit vector and several given vectors
Let $\mathcal{S}$ denote the set of all unit complex-valued $d$-dimensional vectors, i.e.,
$$
\mathcal{S} \triangleq \left\{ \mathbf{s}\in \mathbb{C}^{d} \mid \mathbf{s}^{\mathrm{H}}\mathbf{s}=1 \...
- 550
11
votes
0
answers
445
views
What sequence maximizes the final distance?
This problem was created by professor Ronaldo Garcia from Universidade Federal de Goiás (UFG) and he showed it to me at an event in my university. This problem has a lot of history and he told me he ...
0
votes
1
answer
103
views
Constrained linear optimization problem on $C^1$
I am dealing with a problem of the form ($a<b$)
$$
\displaystyle \max_{v \in C^1([a, b])} \int_a^b v(x)~\mathrm{d}x, \quad \mathrm{s.t.} \int^b_a \big(-o'(x)v(x)-v'(x)o(x)\big)f(x)~\mathrm{d}x \...
1
vote
1
answer
162
views
$1$-Lipschitz map from hyperbolic to Euclidean plane
I'm trying to find a reference to the following statement.
Define a function $f$ from the hyperbolic plane (in the Poincaré unit disc model using polar coordinates) to the Euclidean plane (using polar ...
- 743
1
vote
0
answers
36
views
Does Hoffman constant keep the same after a very tiny perturbation on the polyhedron such that the bases are even unchanegd?
Suppose that $P$ is a polyhedron represented by
$$P:=\{x \in \mathbb{R}^n: A x \le b \} \text{ for }A \in \mathbb{R}^{m\times n},\ b \in \mathbb{R}^m,$$
and $P$ contains interior points. Moreover, the ...
- 33
0
votes
0
answers
145
views
Bound on solutions of $Ax \ge b$
Let $A \in \mathbb{Z}^{m \times n}, b \in \mathbb{Z}^{m \times 1}$.
One can show that if there is a solution of $Ax \ge b, x \in \mathbb{R}^n$ then there is one such that $\|x\|_{\infty} \le c (\|A\|_{...
- 439