All Questions
1,021 questions
8
votes
1
answer
236
views
Paradoxical spherical caps
All spherical caps (i.e. sets $C_L:=\{(x,y,z)|x^2+y^2+z^2=1, z\geq L\}$) admit a paradoxical decomposition in the sense of Banach-Tarski, meaning $C_L \tilde{} 2C_L$; here $\tilde{}$ stands for the ...
- 17.6k
6
votes
1
answer
880
views
Relation of some Euclidean geometry theorems and more conjecture generalizations
In this topic I want to share relation of the Pythagorean theorem, the Stewart theorem and the British Flag theorem, the Apollonius' theorem, the Ptolemy's theorem and the Feuerbach-Luchterhand. Since ...
- 1,044
14
votes
1
answer
2k
views
Dao's theorem on six circumcenters associated with a cyclic hexagon
This questions from Ngo Quang Duong's paper
In 2013, O. T. Dao published without proof a theorem with title Another seven circles theorem in Cut the Knot, a free site for popular expositionsof many ...
- 1,044
2
votes
1
answer
573
views
Conjectute: no exist an equilateral triangle such that all vertices are integer numbers [closed]
I am looking for a solution for a conjecture as follows.
In Cartesian plane, no exist an equilateral triangle such that three vertices are integer numbers.
I hope that you like the question and ...
- 1,044
2
votes
2
answers
438
views
Perturbation of Linear Programs
Consider the linear program,
$$\begin{array}{ll} \text{maximize} & c^T x\\ \text{subject to} & Ax \leq b\\
& x \geq 0\end{array}$$
I want to study the sensitivity of the optimal $x^*$ ...
- 275
5
votes
1
answer
433
views
Sixteen points circle - A conjecture on Möbius plane
The conjecture refer the reader about the Bundle's theorem configuration. (This conjecture from a note)
Consider the Bundle theorem configuration :
Points $A_1, A_2, A_3, A_4$ lie on a circle,
...
- 1,044
0
votes
1
answer
204
views
Is the linear production game a convex game?
In cooperative game theory, the linear production game (LPG) is defined by letting the characteristic function have the form of a linear programming problem.
Does anyone know if the LPG is a convex ...
- 17
1
vote
1
answer
391
views
Efficiently Generating the Convex Hulls of Two Polytopes and Counting Faces
Suppose you have two polytopes $P_1, P_2 \in \Bbb{R}^n$ given by
$$ P_1 = \lbrace x: A_1 x \le b_1\rbrace$$
$$ P_2 = \lbrace x: A_2 x \le b_2\rbrace $$
I wish to find their convex hull, that is a ...
- 2,689
4
votes
2
answers
320
views
Inequality from a point in plane to a triangle OR Inequality on a quadrilateral
If points $A$, $B$, $C$ form a triangle in euclidean space and $D$ is another point in the plane of the triangle, the problem is to show that :
$\frac{AB}{DA + DB} + \frac{BC}{DB + DC} \ge \frac{AC}{...
- 55
2
votes
0
answers
177
views
Formulating shortest path as submodular minimization
I'm curious about the general question of whether any combinatorial optimization problem with polynomial time solution can necessarily be reformulated as minimizing a submodular function.
The answer ...
- 21
2
votes
0
answers
168
views
Which Coxeter groups can be realized as affine reflection groups?
Every affine reflection group has a Coxeter presentation (https://en.wikipedia.org/wiki/Reflection_group#Relation_with_Coxeter_groups). How do you tell which Coxeter presentations arise from affine ...
- 2,130
6
votes
1
answer
263
views
Algorithm that solves every Mixed Integer Linear Program (to optimality)?
Given a Mixed Integer Linear Program with rational coefficients (both for the objective functions and all constraints), is it always possible to solve it algorithmically?
I know that you usually ...
- 1,282
2
votes
0
answers
112
views
Pcross-like, nonogram-like in near-linear time [closed]
I have a problem with a puzzle game like pcross in which I have a nxn square: At any index of rows and columns I have an integer that say the maximum numbers of points that I can place in that row/col....
2
votes
1
answer
531
views
Complexity of Deciding Feasibility of a system of linear inequalities over restricted variables
I am working out an interesting problem and would like some help with this particular sub problem:
Suppose we have a matrix $ M =\left\lbrace a_{ij}\right\rbrace $ of size $n\times m$ where $ a_{ij}\...
- 21
10
votes
2
answers
764
views
Generalization of Stewart's theorem?
I'm curious about the generalization of Stewart's theorem to more dimensions. MathWorld mentions that there is a generalization done by Bottema, but I could not find much information on it. All I ...
- 163
3
votes
1
answer
107
views
Existence or otherwise of a set of "sufficiently intricate" open sets
Fix $d \in \mathbb{N}$. Do there exist mutually disjoint connected open sets $V_1,\ldots,V_n \subset \mathbb{R}^d$ and $\mathbf{v} \in \mathbb{R}^d$ such that
$\mathbb{R}^d \setminus (\bigcup_{i=1}^n ...
- 708
0
votes
1
answer
543
views
Convert general optimization problem to LP problem
I am trying to convert the following problem into a linear programming problem:
There are $M\times N$ matrix $T$ of real numbers between 0 and 1 and $N\times 1$ vector $w$ of real numbers between 0 ...
- 99
21
votes
3
answers
2k
views
Probability of two vectors lying in the same orthant
Let $S^{d-1} = \{x \in \mathbb R^d: \|x\| = 1\}$ denote the unit sphere in $\mathbb R^d$. Let $v$, $w$ be drawn uniformly at random from $S^{d-1}$, conditioned on their inner product being equal to $\...
- 733
5
votes
1
answer
684
views
Is every complex rational algebraic variety simply connected for the Euclidean topology?
Is it true that every quasi-projective rational irreducible algebraic complex variety is simply connected for the Euclidean topology?
Of course, this is false if we replace "complex" with "real" or ...
- 7,722
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
0
votes
1
answer
2k
views
When to use non-negative-least square and least-square [closed]
What are the typical case we need to use Non-negative least squares NNLS
$$
||Ax - B||^2
$$
instead of least-square $$ Ax-B$$ (or vice versa)?
And is there any drawback in applying them on large $A$...
- 135
3
votes
1
answer
260
views
Better alternative to solve quadratic programming for large matrices
I have the following problem. Let's say we have $x_{jk}$ it is an expression value of gene $j$ in a sample $k$. It is the average of expression levels across the cell types $s_{ij}$, weighted by ...
- 135
13
votes
1
answer
921
views
Limiting shape for Brillouin zones
Is it true that the limiting shape for Brillouin zones (for any lattice) is a circle?
You can find the definition and the step by step construction of Brillouin zones here. This picture is taken from ...
- 12.3k
5
votes
1
answer
268
views
what's the formula of the inradius of a general simplex? [closed]
As the title, I just want to know whether there is a general formula for calculating the inradius of a n-simplex. Thank you!
- 51
7
votes
2
answers
359
views
Closed curve whose neighborhood is as large as possible
Let $C$ be a closed curve in the plane and let $N_\epsilon(C)$ be an $\epsilon$-neighborhood of $C$, like this:
(ignore the fact that the "curve" is polygonal in this picture, I drew it in MATLAB)
...
- 4,049
5
votes
0
answers
193
views
Determining N d-points yielding equal sums of Euclidean distances from M s-points
Given M source points (s-points), determine N, the number of destination points (d-points), and their locations (coordinates), such that the sum of the N Euclidean distances from each source point to ...
- 51
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
319
views
Is it possible to construct an isosceles triangle by using a ruler and without using a pair of compasses?
It is well known that on Euclidean plane one can construct an isosceles triangle on given straight line by using a ruler and a pair of compasses.
Also it is possible to construct straight line ...
- 774
0
votes
1
answer
82
views
Introducton books for $\frak{E}_p(I)$
Are there any good books different from abstract harmonic analysis by hewitt to study $\frak{E}_p(I)$. where $\frak{E}_p(I)$ is: Let $I$ be an arbitrary index set. For each $i\in I$ let $H_i$ ...
- 209
5
votes
1
answer
146
views
How does one go from convexity to submodularity?
If I have a function which is convex in the hypercube, $[-1,1]^n$ then when would it imply that its restriction to $\{-1,1\}^n$ is submodular?
It would be helpful is someone can share some specific ...
- 1,893
1
vote
1
answer
219
views
approximate diameter of polytopes in high dimensions
I just came across the following problem:
Let us consider the unit corner of the n-cube
$$
\Delta^n = \left\{(t_1,\cdots,t_n)\in\mathbb{R}^n\mid\sum_{i = 1}^{n}{t_i} \leq 1 \mbox{ and } t_i \ge 0 \...
- 75
17
votes
1
answer
1k
views
A problem in elementary geometry
Let us have a triangle ABC in the Cartesian plane and consider the following transformation of this triangle:
On the ray AB starting at A, select a point B' so that so that |AB'|=|AC|. Likewise,
...
- 783
2
votes
0
answers
154
views
Listing all Lattice Points in a Box
Let $B := [-1,1]^n$ be an $n$-dimensional box. Moreover, let $v_1,\ldots,v_n \in \mathbb{R}^n$ form a basis of $\mathbb{R}^n$, where the entries of the $v_i$ are explicitly irrational. We can assume ...
- 173
3
votes
2
answers
792
views
Has anyone developed a technique to generate a polytope given (possibly redundant) inequality constraints? [closed]
I've found a few papers that deal with removing redundant inequality constraints for linear programs, but I'm just trying to find the vertices for a feasible region, given a set of inequality ...
- 131
1
vote
0
answers
171
views
Finding all feasible solutions
Let $u$ be a $n_{max} \times m$ matrix. Let $z$ be a $n_{max} \times s_{max} \times n_{max}$ cube. Let $w$ be a $n_{max} \times 1$ vector. All the three matrices can have values from the set $\{ 0, 1\}...
- 175
12
votes
1
answer
1k
views
Maximal Number of Pairs of Orthogonal vectors in a set of $n$ vectors in $\mathbb{R}^3$
Suppose you are given a set of $n$ non-zero vectors in $\mathbb{R}^3$. What is the maximum number of pairs of them that are orthogonal? The current guess is $\le 2n$.
EDIT: I forgot to add that no ...
- 928
2
votes
0
answers
210
views
Finding optimal linear transformation for intersection of convex polytopes
I previously posted this on MathSE and am now trying here.
I have the following situation, as shown in the following diagram:
$W=\{w_i\}_{i=1..|W|}$ is a set of vertices (show in diagram in blue) ...
- 695
1
vote
0
answers
120
views
The column generation technique on a Train Unit Assignment Problem [Linear Programming]
I am doing an assignment where I need to implement a mathematical model that I can't wrap my head around. For the technique of column generation, one would need to my understanding, a master problem ...
- 111
3
votes
4
answers
513
views
Terminology for polygons
As you may know term "polygon" might mean few different things
and its meaning has to guessed from context.
By some reason I have to use few of these meaning in one place.
So I converge to the ...
- 45k
1
vote
2
answers
1k
views
Pairwise distance distribution for point clouds (normal distribution) [closed]
I have a point cloud (2D for now) of $N$ normally distributed points (with a certain $\sigma$).
My first question would be how the pairwise distance distribution looks (just by chance I discovered a ...
user76454
4
votes
1
answer
3k
views
Find the minimum distance between two convex hulls
We work over $\mathbb{R}^N$. Let $\mathbf{P}_1$ denote the hyperplane constructed using $N$ points, each of which is on a different axis (there are $N$ axes). We denote by $\mathbf{P}_2$ the convex ...
- 233
3
votes
1
answer
362
views
Equality of Euclidean numbers / constructible numbers
Euclidean numbers are those real number that can be constructed from the natural numbers by a finite chain of +,-,*,/ and $\sqrt{}$. They are also called Constructible Numbers.
I am now interested in ...
- 1,282
5
votes
1
answer
183
views
Resource Constrained Routing with Refueling
What are good algorithms (resp. models) for calculating optimal or near optimal routes while taking into account fuel consumption, options for refueling and, limited tank capacity?
Especially modeling ...
- 13.2k
4
votes
1
answer
891
views
Basic result in semi-infinite linear programming
Consider a standard linear program of the form $$\textrm{minimize}_x~~~~ c^Tx~~~~ s.t. \\ Ax = b \\ x \geq 0$$ with $x\in \mathbb{R}^n$ and $A \in \mathbb{R}^{m \times n}$. It is well known that, if ...
- 4,049
2
votes
1
answer
186
views
How can I find the maximum value of this function?
For given values of $A \in \mathbb{R}^{m \times n}, b \in \mathbb{R}^m$, how can I find the value of:
$$
\max_{x \in [0,1]^n} \|Ax+b \|_1
$$
Or is this problem NP-hard?
- 23
11
votes
1
answer
524
views
Elementary proof of a triangular grid lemma
I am looking for an elementary proof of the following lemma, which concerns what Green and Tao call "triangular grids" (see arXiv:1208.4714).
Let $a_1$, $a_2$, $a_3$, $a_4$, $b_1$, $b_2$ be six ...
- 1,174
8
votes
1
answer
265
views
Penrose tiling substitution is bijective
Let $\mathcal{P}$ a Penrose tiling built by a substitution $\omega$ with two triangles.
It is claimed, for instance, in the article of Anderson and Putnam "Topological invariants for substitution ...
- 81
2
votes
1
answer
229
views
Algorithm to find the vertices of the equidistant lines between N closed polygonal lines
I have a set $\{C_1, C_2, \ldots, C_N\}$ of $N$ nonintersecting closed piecewise linear curves on the Euclidean plane. For every point $x \in \mathbb{R}^2$ we say it belongs to a territory serviced by ...
- 329
7
votes
2
answers
949
views
Explicitly describing the region of the plane "outward of" a simple, open, oriented, cubic curve $c:(0,1)\to\mathbb{R}^2$
Some Context:
I'm working with some data given in the form of Bezier curves. I need to sort these (partially ordered) Bezier curves by "outwardness" (described below) and have come across an ...
- 279
2
votes
0
answers
56
views
Projecting a convex partition onto a convex set
Say that $X$ and $Y$ are two convex regions in the plane, and suppose that $X \subset Y$. Further suppose that $Y$ is partitioned into disjoint convex subsets $Y_1 ,\dots, Y_n$. Is there a way of ...
- 4,049