All Questions
279 questions with no upvoted or accepted answers
4
votes
0
answers
225
views
Studying finite groups with Euclidean geometry?
Since each finite group $G$ can be considered as a subgroup of the symmetric group, by Cayley's theorem, we might see the elements of $G$ as permutations $\pi$.
Consider for each $\pi \in G$ the set:
...
user6671
4
votes
0
answers
98
views
Collections of points maximally spaced with respect to one another
The icosahedron and dodecahedron are well known to share symmetry groups. This partially accounts for the fact that one can form a type of compound of the two where each of the vertices in the ...
- 3,209
4
votes
0
answers
161
views
Trilinear polarity from AG perspective
Consider a triangle $ABC$ in the projective plane $\mathbb{P}^2.$ For a point $p \in \mathbb{P}^2$ one can define its trilinear polar line $t(p)$ (see here). This defines a birational map to the dual ...
- 4,316
4
votes
0
answers
203
views
$\ell^1$-norm minimization duality
I am looking for an explicit description and discussion of the dual of the $\ell^1$-norm minimization problem $\lVert A x\rVert_1\to\min$, where $A$ is a matrix, and $x$ belongs to the $n$-simplex $\...
- 17k
4
votes
0
answers
539
views
Using Linear Programming as an iterative procedure
Suppose, we have a linear program and an optimal solution to it. Suppose now, we get a new constraint. We want to obtain an optimal solution to the given linear program extended by that new constraint....
- 391
4
votes
0
answers
184
views
Optimal instructions for the modular construction of rectlinear Lego structures
Let $X$ be a compact (or periodic) union of integer translates of unit cubes such that the interior of $X$ is connected. (If it makes any difference, suppose that the dimension $n$ of $X$ is 3.) I am ...
- 15.4k
4
votes
0
answers
250
views
Finite subgroups of the unimodular group
This is related to this MO question (and others as well).
Hoping that this will not turn out to be too broad, I would like to know about the 'state of the art' of:
1) The problem of classifying ...
4
votes
0
answers
790
views
Is it possible to use linear programming to solve this problem?
I am trying to write software to minimize pricing for cell phone subscription services, ie: choose the optimum plan for each customer in a large group.
Could someone comment on whether this is ...
- 41
3
votes
1
answer
145
views
Triangle centers formed a rectangle associated with a convex cyclic quadrilateral
Similarly Japanese theorem for cyclic quadrilaterals, Napoleon theorem, Thébault's theorem, I found a result as follows and I am looking for a proof that:
Let $ABCD$ be a convex cyclic quadrilateral.
...
- 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
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
3
votes
0
answers
282
views
Continuum of Lagrange multipliers, duality gap, and minimax theorem
Suppose I have a linear optimization problem involving random variables on some (infinite) probability space $\Omega$. For example, need to maximize expectation $E[Q]$ of random variable $Q$ subject ...
- 781
3
votes
0
answers
301
views
A problem on configuration of Dao's theorem on six circumcenters
Abstract: In the figure belows: Three lines through center of pair opposite red circle are concurrent. This is a statement of Dao's theorem on six circumcenter, a new theorem in plane geometry which ...
- 1,776
3
votes
0
answers
87
views
Additional symmetries of the Traveling Salesman Polytope
Given the complete graph $K_n=(V,E)$, the Traveling Salesman Polytope is a convex polytope in $\Bbb R^E$ obtained as the convex hull of the indicator vectors of (edge-sets of) Hamiltonian cycles in $...
- 13.6k
3
votes
0
answers
122
views
Convex optimization upper bound for a non-linear optimization
Is there any good convex optimization problem based upper-bound for the following non-linear optimization problem?
\begin{align}
\max_{x_1,\ldots,x_N}&\quad \sum_{n=1}^{N} \log(1+\frac{x_n}{1+\...
- 287
3
votes
0
answers
73
views
On isospectral planar domains (and a paper by Buser, Conway, Doyle and Semmler)
I have never seen a short, elegant way (from the viewpoint of a non-topologist) which constructs isospectral planar domains from Sunada group triples, although essentially those triples live at the ...
- 4,547
3
votes
0
answers
60
views
A canonical map from a Euclidean cone-manifold $M^3$ to $\mathbb{E}^3/\mathrm{Hol}(M)$
Suppose we have a 3-dimensional Euclidean cone-manifold $M$—in my book that just means $M$ is a manifold whose geometry is constructed by gluing it out of Euclidean tetrahedra, with faces paired by ...
- 458
3
votes
0
answers
163
views
A new "adversarial" Wasserstein distance?
Let us consider $\mu_1, \mu_2$ and $\mu_3$ three probability measures living on $[0,1]^{k_1}, [0,1]^{k_2}$ and $[0,1]^k$respectively, with $k_1 +k_2=k$. Let us denote by $\Gamma(\mu,\nu)$ the set of ...
- 555
3
votes
0
answers
178
views
Uniqueness of projection under spectral norm
I am considering
$$
\min_{M\in \mathcal{M}} \|X - M\|:=x \neq 0,
$$
where $X$, $M$ are $m\times n$ matrices, $\|\cdot\|$ is spectral norm and $\mathcal{M}$ is a matrix subspace. I wonder to what ...
- 131
3
votes
0
answers
149
views
Is the Mandelbrot set weakly self-similar?
A subset $F$ of an Euclidean space $E$ will be called weakly self-similar if for all $x \in F$ there is $\epsilon_x>0$ such that for all positive $\epsilon \le \epsilon_x$ there are $y \in F$, $\...
3
votes
0
answers
905
views
A generalization of the Sawayama-Thebault theorem
1. Introduction
The Sawayama-Thebault theorem is one of the best nice theorem in plane geometry. The theorem has a long history. It was published in AMM in 1938 the first solution appeared in 1973 ...
- 1,776
3
votes
0
answers
105
views
Szemeredi-Trotter bounds when the lines are implicitly described by a point set
Recall:
Theorem (Szemeredi-Trotter): Given $n$ distinct points and $\ell$ distinct lines in $\mathbb{R}^2$, the number of point-line incidences is $O(n + \ell + (n \ell)^{2/3})$.
Now, instead of $\...
- 1,389
3
votes
0
answers
214
views
Volume of intersection of a ball and cube with arbitrary position in $n$ dimension
Let $ A(n, r, x) = B^n_r(x) \cap [0,1]^n $ denote the intersection between an $n$ ball $B^n_r(x)$ with arbitrary radius $r$ and arbitrary center $x \in \mathbb{R}^n$ that intersects a unit $n$ cube $ [...
- 365
3
votes
0
answers
105
views
Are there scenarios under which feasibility bilinear programming is easy?
Given $c\in\Bbb R^{n_1},d\in\Bbb R^{n_2}$, $E\in\Bbb R^{n_1\times n_2}$, $A\in\Bbb R^{m_1\times n_1}$, $B\in\Bbb R^{m_2\times n_2}$ $a\in\Bbb R^{m_1}$, $b\in\Bbb R^{m_2}$ and $t\in\Bbb R$ we know ...
- 13.9k
3
votes
1
answer
368
views
Lot sizing problem: how to add these cuts efficiently
Consider the set of constraints of the uncapacitated lot sizing problem:
$$
\{(x,s,y)\in \mathbb{R}^n_+ \times \mathbb{R}^n_+ \times \mathbb{B}^n \;|\;s_{t-1}+x_t = d_t+s_t,\; x_t \le My_t,\; t=1,\...
- 225
3
votes
0
answers
63
views
Exact Value of a Constant Related to the Quickhull Algorithm
What is the exact value of the infinite sum
$$ \sum_{n=1}^{\infty}n2^n\sin\left(\frac{\pi}{2^n}\right)\left(1-\cos\left(\frac{\pi}{2^n}\right)\right)$$
That constant is related to the Quickhull ...
- 13.2k
3
votes
0
answers
71
views
Dependence of optimization problem on the linear constraints
Let $I=\{x_1,\cdots, x_n\}\subset \mathbb R$ be fixed. Given two probability distributions $\alpha=(\alpha_i)_{1\le i\le n}$ and $\beta=(\beta_i)_{1\le i\le n}$ on $I$, and a matrix $c=(c_{i,j})_{1\le ...
- 1,835
3
votes
0
answers
80
views
Equidistribution of Brillouin zones
Answering the question about Limiting shape for Brillouin zones Victor Kleptsyn proved that $N$th Brillouin zone is very close to a circle of radius $c\sqrt N$ (you can find all necessary definitions ...
- 12.3k
3
votes
0
answers
970
views
Testing if a point is inside a convex polytope formed by halfspaces in n-dimension
Assume we have a convex polytope that is formed by the intersection of $k$-halfspaces in $\mathbb{R}^{n}$.
$$
a_{0,0}x^{n-1} + {a}_{0,1}x^{n-2} + ... a_{0,n-1} \leq 0
$$
$$
a_{1,0}x^{n-1} + {a}_{1,...
- 31
3
votes
1
answer
966
views
Continuity of minimizers to distance function from point to convex set
Suppose I am minimizing the Euclidean distance in $\mathbb{R}^{n}$ between a point $y$ and compact convex set $U$ (where $y\notin U$):
$\min_{x\in U}\|x-y\|$.
I believe the minimizer $x_{U}^{*}$ is ...
- 81
3
votes
0
answers
48
views
Number of not self-intersecting closed paths spanning $n$ iid uniform points
Let $X_1,X_2,\dots,X_n$ be independent uniform variables in the square. What is the number of piece-wise linear paths which vertices are all the $X_i$ and that do not self-intersect? In other words, ...
- 1,352
3
votes
0
answers
3k
views
0,1 solution to system of linear integer equations
I have the following problem:
$A x = b$
where $A, b$ - $m \times n$-matrix and $m$-vector of nonnegative integers (respectively).
$x \in \{0,1\}^n $ - vector of binary variables, which need to be ...
- 149
3
votes
0
answers
220
views
Could SVD be used to optimize the partial inner-products?
Suppose a set $N$ of $n$ distinct points in $m-$dimensional space is given in $X\in\mathbb{R}^{n\times m}$. Also, suppose a subset $L\subset N$, $|L|=l<m<n$, with
$m-$dimensional coordinates in ...
- 131
3
votes
0
answers
312
views
Linear complementarity problem: principal pivoting algorithm
I'm trying to implement the "Dantzig; van de Panne and Whinston" principal pivoting algorithm for solving symmetric positive semi-definite LCPs from "The Linear Complementarity Problem" book (...
- 151
2
votes
0
answers
69
views
Pólya's orchard problem among Gaussian primes
Quoting myself from an earlier post:
Pólya's orchard problem asks for which radius $r$ of trees at each lattice point within a distance $R$ of the origin block all lines of sight to the exterior of ...
- 151k
2
votes
0
answers
37
views
Theta series of well-rounded lattices
I've started looking into well-rounded Euclidean lattices and I was interested in learning whether their theta series have any interesting properties, but haven't found much in terms of bibliography ...
- 223
2
votes
0
answers
114
views
Another Butterfly theorem — Conway like circle
Have You seen these result as follows before?
In Figure 1: $AA'=BB'=tAB$; $CC'=DD'=tCD$, where t is real number then $ABCD$ is a cyclic quadrilateral iff $A'B'C'D'$ is a cyclic quadrilateral.
In the ...
- 1,776
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
2
votes
0
answers
259
views
Least number of circles required to cover a continuous function on $[a,b]$
I asked this question on MSE here.
Given a continuous function $f :[a,b]\to\mathbb{R}$, what is the least number of closed circles with fixed radius $r$ required to cover the graph of $f$?
It is ...
- 541
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
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}$ (...
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
2
votes
1
answer
879
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} &...
- 1,171
2
votes
0
answers
59
views
Historical question about tangent lines to disjoint circles
It is pretty well known that two disjoint circles have 4 different lines that are simultaneously tangent to both circles. There are constructions with ruler and compass available in many books, but I ...
2
votes
0
answers
83
views
Principal diagonals of octagon meet in a single point
Can you provide a proof for the following claim:
Claim. Given octagon circumscribed about an ellipse. If the vertices of the octagon lie on another ellipse then its principal diagonals meet in a ...
- 2,661
2
votes
0
answers
76
views
Polyhedron coordinate bound
Given a polyhedron
$$Ax\leq b$$
where we assume $A\in\mathbb Q^{m\times n}$ and $b\in\mathbb Q^{m}$ and it takes $L$ bits to represent the inequalities what is a good bound on the quantity $\|y\|_\...
- 13.9k
2
votes
0
answers
115
views
Sufficient coordinate-free condition for points being co-spheric
Question:
is there a theorem that guarantees that
$\mathcal{P}\subset\mathbb{E}^n$ is finite set of points in a Euclidean space and all radii of the $(n-1)$-spheres that are defined by the $n$-...
- 13.2k
2
votes
0
answers
80
views
Can an exterrior of a ball in Euclidean space be considered a ball itself under any proposed generalization?
If we take an n-dimensional Euclidean space and cut off a ball centered at origin, we get a set that has boundary equal to the surface area of the cut off ball.
I wonder whether there were any ...
- 10.1k
2
votes
0
answers
46
views
Notion of distance between linear programs
Consider the linear programming problem
\begin{align}
\max_{x}&~c^Tx \\~s.t.~~a^Tx &\leq B~,~0\leq x_i \le1
\end{align}
where $c$ and $a$ are $n \times 1$ given non-negative vectors. $B$ is a ...
- 1,421
2
votes
0
answers
66
views
Proving the existence of a dual for an infinite linear program
I am concerned with proving the existence of the dual of an infinite linear program. In addition to the writings of Rockafellar, Luenberger, and Boyd & Vandenberghe on: subdifferentials, Legendre-...
- 121