All Questions
1,022 questions
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
1
vote
0
answers
85
views
Smallest sum of original column entries in 2d matrix [closed]
I have an interesting optimization problem I am trying to solve now and I thought I'd share it here in order to find the best answer. The problem itself is not complicated and it is stated like this:
...
- 111
18
votes
1
answer
875
views
What sort of models did Bolyai and Lobachevsky use to demonstrate the consistency of their models of non-Euclidean Geometry?
As is well-known, in the 1820s both Bolyai and Lobachevsky showed, at long last, the independence of the Parallel Postulate from the rest of the axioms of Euclidean geometry by developing what we now ...
- 15.3k
6
votes
1
answer
718
views
What is the distribution of the maximum nearest-neighbor distance of a point cloud sampled from a solid body like?
Let $\mathcal{B} \subseteq \mathbb{R}^n$ be an $n$-dimensional solid body. Assume that we sample $N$ points, say $S = \{ x_1, ..., x_N \}$, from $\mathcal{B}$ uniformly at random. Consider the ...
14
votes
0
answers
261
views
Dividing a convex region to minimize average distances
Let $C$ be a convex region in the plane with area 1 that contains distinct points $p_1,\dots,p_n$. Say I'd like to divide $C$ into $n$ pieces $C_1,\dots,C_n$, each of area $1/n$, and I'd like to ...
- 4,049
6
votes
1
answer
410
views
Segments on a family of parallel lines
Let $J$ be a family of parallel closed intervals in the plane $\mathbb{R}^2$, no two different of them contained in any common line. Moreover, for arbitrary three intervals belonging to $J$ there ...
- 63
3
votes
1
answer
1k
views
Constrained vs Unconstrained Optimization
I'm currently working on an optimization problem with a linear objective with linear and nonlinear constraints, i'm facing difficulties reaching a good solution, so i was advised to move the nonlinear ...
- 31
2
votes
0
answers
265
views
How large can a set of nearly equidistant points be?
Suppose that $D$ is a set of points in $\mathbb{R}^{k}$ such that all pairwise distances between them belong to $[1,1+\epsilon]$.
It seems that such a set cannot be very large and that its ...
- 6,962
8
votes
2
answers
339
views
Angle subtended by the shortest segment that bisects the area of a convex polygon
Let $C$ be a convex polygon in the plane and let $s$ be the shortest line segment (I believe this is called a "chord") that divides the area of $C$ in half. What is the smallest angle that $s$ could ...
- 113
1
vote
1
answer
207
views
Computing probability that $Ax\geq0$ where $x$ is a vector of iid gaussians and $A$ is matrix of $1$s and $0$s
This question came up in my research: What is the probability that $Ax\geq0$ where $x$ is a vector of iid gaussians and $A$ is matrix of $1$s and $0$s?
So far I only figured out that I can do Monte ...
- 113
6
votes
0
answers
97
views
Finding the optimal mixture of two convex functions
I am trying to find an efficient way to solve the problem $$\min_{p,x_1,x_2} p\cdot f(x_1)+ (1-p) \cdot f(x_2)~~~~~ s.t.\\p\cdot g_1(x_1) + (1-p)\cdot g_2(x_2)\leq 1 \\ 0\leq p \leq 1$$ where $x_1,x_2\...
2
votes
0
answers
148
views
Derivation of gradient of SSE in Geodesic Regression
On page 79 (or page 5) of this this paper the gradient of the SSE of the Geodesic model is described explicitly. My question is how are these equitations derived in detail; where can I find the ...
- 5,405
1
vote
1
answer
2k
views
Computation of extreme rays of rational polyhedral cones - Hemmecke's project and lift algorithm
I am working on an implementation of Raymond Hemmecke's algorithm for finding generating sets of cones: http://arxiv.org/abs/math/0203105
Unfortunately I am struggling to make the algorithm work on ...
- 11
2
votes
0
answers
71
views
Select n vectors from k vectors (in 3D) such that each component of the resultant vector >= each component of a given vector M
this was left unanswered for 1 week on MStackExchange, so I thought MOverflow would be more appropriate. Thanks :)
Let $R = (R_x, R_y, R_z)$ be the resultant vector of the n vectors and $M = (M_x, ...
- 21
6
votes
1
answer
208
views
Did Lucas discover Lucas circles?
MathWord's article on Lucas circles traces the name to a little-known 1973 publication. These interesting circles have found their way into several 21st century publications, including the online ...
- 3,443
8
votes
0
answers
200
views
Ricocheting pinball-like shot: Complexity?
Suppose one has $n$ perfect two-sided mirror segments in the plane $\mathbb{R}^2$.
The segments are open, excluding their endpoints.
They are disjoint as closed segments, i.e., no pair shares an ...
- 151k
4
votes
1
answer
171
views
Geometric realization of an abstract triangulation of the plane
Can every abstract simplicial complex whose geometric realization is homeomorphic to $\mathbb{R}^2$ be realized by a rectilinear triangulation of the Euclidean plane? Alternatively put, can a curvy (...
- 3,376
2
votes
0
answers
189
views
Examples of Geometric Constructions in Higher Dimensions
The classical problem of geometric construction seems to be restricted to planar Euclidean Geometry with straight edge and compass as the only admissible "construction-tools".
I would like to know,...
- 13.2k
2
votes
0
answers
149
views
How to solve the following generalized quadratic programming problem [closed]
I want to solve a generalized form of a quadratic programming problem
$$\min_x \left(\sqrt{x^TPx}+\sqrt{x^TQx}\right)^2+c^Tx$$,
$$\textrm{ s.t. } Ax\le b.$$ Here, $P$ and $Q$ are both positive ...
- 21
2
votes
1
answer
426
views
Network flows with shared capacities
Suppose we have a flow network, with capacity constraints on weighted sums of arc flows, such as:
$$2 f(1, 2) + 3 f(4, 5) + f(3, 7) \leq 10,$$
where $f(1, 2)$ denotes the flow through arc $(1, 2)$....
- 23
5
votes
0
answers
167
views
A specific case of the $p$-center problem
Given a fixed positive integer $m$, let $\cal{S}$ be the subset from $\mathbb{R}^m$ defined as $\cal{S} = \{u \in \mathbb{R}^m \mid \forall i \in \{1, \dots, m\}, u(i) > 0$ and $\sum_{i=1}^m{u(i) = ...
- 125
1
vote
1
answer
175
views
accelerate convex optimization by proximal projection
I am using level method to solve non-smooth convex programming problem (where the objective function is given by an oracle from another program ):
http://www2.isye.gatech.edu/~nemirovs/Lect_EMCO.pdf
...
- 867
5
votes
1
answer
384
views
Examples of Polyhedra with Large Shadows
Let $P \subseteq \mathbb{R}^n$ be a polyhedron described by $\mathcal{O}(n^{c_1})$ inequalities, where $c_1$ is a constant. Moreover, let $M\colon P \to \mathbb{R}^2$ be a linear mapping. I'm looking ...
- 321
4
votes
1
answer
749
views
Focus of parabola using only a ruler
It is an easy exercise that using ruler and compass one find the focus of a given parabola.
Can one do the same using only a ruler? -- if not, why?
- 1,437
2
votes
1
answer
276
views
An optimization problem in complex space
Consider the following optimization problem
$$
\min \| \textbf{Ax-B}\|
$$
$$
s.t.|x_i|=1,i=1,...,n
$$
where $\textbf{x}\in \mathbb{C}^{n}$ is the optimization varaible, $x_i$ is the $i$-th ...
- 21
5
votes
1
answer
2k
views
Algorithm to minimally connect line segments in Euclidean plane
Suppose you have finitely many line segments in the Euclidean plane. How do you "connect them to form one chain of line segments of minimal length?"
More formally and generally, what I'm looking for ...
- 153
2
votes
1
answer
164
views
Measuring the Randomness and Statistics of Convex Polygons
How can I tell, how likely it is, that a given convex polygon with a sufficiently high number of edges is random and, if so, what kind of randomness it is (e.g. white noise)?
What is known about ...
- 13.2k
7
votes
1
answer
224
views
A polytope with a bound on the sum of any $k$ variables
Let $2\le k\le n-1$ and define the polytope
$$P_k(n) = \lbrace (x_1,\ldots,x_n) \in \mathbb{R}^n :
-1\le x_{i_1}+\cdots +x_{i_k} \le 1 \text{ for all } 1\le i_1\lt\cdots\lt i_k\le n\rbrace.$$
There ...
- 37.7k
10
votes
5
answers
1k
views
ten concurrent lines
this relates to a question asked at MSE. i was able to find an answer using complex numbers.
here is the question: there are five points on a circle. take any three points, through the centroid of ...
- 291
9
votes
0
answers
426
views
How can we join two points with a small ruler? [closed]
We want to join by a line two distinct points $A$ and $B$. We have only a ruler of length $l>0$ and a pen. If $AB>l$ how can we do this? Imagine a method that works when $AB$ is really huge and ...
- 1,759
12
votes
1
answer
1k
views
How large can you draw an island on a map?
A cartographer friend asked me this question: could you classify (shapes of) islands by how much space they occupy on a map (comparatively to how much space is occupied by water) if you draw them as ...
- 1,347
2
votes
1
answer
173
views
Calculating the "Belvedere Hull" of a Simple Planar Polygon
As an informal motivation the problem, imagine a tower with polygonal footprint, that is located in a beautiful landscape, the "Belvedere Hull" is then related to the directions, in which one would ...
- 13.2k
32
votes
2
answers
1k
views
Term for "uncheckable constructions"
Is there a term for "uncheckable geometric constructions"?
Say, Angle Trisection and Doubling the Cube are checkable;
i.e., if the answer is given one can do finite Compass-and-straightedge ...
- 45k
2
votes
1
answer
104
views
Standard names and methods for this type of fitting minimization
In material science research, we have come across the following type of problem.
Given a m by n matrix A, a m vector b, and error tolerance $\varepsilon$, we want to do this minimization
$$\eqalign{
...
- 867
3
votes
1
answer
197
views
Three-dimensional Apollonian spirals
Given mutually (externally) tangent spheres $S_1$, $S_2$, $S_3$, $S_4$, let $S_n$ be the unique sphere externally tangent to $S_{n-1}$, $S_{n-2}$, $S_{n-3}$, and $S_{n-4}$ for $n \geq 5$.
Let $P_{\...
- 19.7k
8
votes
4
answers
530
views
Inside-out polygonal dissections
A dissection of a polygon $P$
is a partition of $P$ into a finite number of pieces, which can then be rearranged
(via planar translations and rotations) and joined (without overlap) to form a new ...
- 151k
8
votes
2
answers
371
views
Are angles between points enough to decide the realizability?
Let n points in the plane be given whose coordinates we don't know.
Assume, however, that for any triple of the points we know the angle.
Question: Can we decide whether the n points are realizable ...
- 245
0
votes
1
answer
163
views
Existence of half-planes with respect to regular open sets of the Euclidean plane
I initially asked this question at math.stackexchange.com but there was no reaction, so I thought this may be a good idea to transfer it to mathoverflow.net
Let $\langle\mathrm{r}\mathscr{O},\mathord{...
- 1,112
8
votes
2
answers
246
views
Are sums of 0-1 Pareto efficient vectors Pareto efficient?
Does there exist $m,n\ge1$, an $m \times n$ matrix $A$, and a vector $x \in \mathbb{R}^n$ such that:
The entries of $A$ are $\in \{0, 1\}$.
For all pairs of columns $u, v$ of $A$ the entries of $u - ...
- 388
0
votes
2
answers
118
views
Inner Product of Given Sum Positive Sequence
Let $$A = \Big\{(a_1,a_2,\dots)\ \Big|\ a_i\ge 0, \sum_{i=1}^\infty a_i=1\Big\},$$ $$v(x)=\sup\left(\bigg\{\sum_{i=1}^\infty a_ib_i\ \bigg|\ (a_i)_{i=1}^\infty,\, (b_i)_{i=1}^\infty \in A,\,\sup\...
- 2,239
11
votes
1
answer
919
views
Generalized Hlawka inequality
Let $E$ be a vector space over the real (the complex case is interesting too). We consider functions $f:E\rightarrow\mathbb R$ which satisfy the homogeneity property
$$f(\lambda x)=|\lambda|\,f(x).$$
...
- 52.3k
2
votes
1
answer
301
views
books on very large scale linear optimization
Recently in my material science research, I have encountered problems of very large scale linear optimization. I read the introductory book "Introduction to Linear Optimization (Athena Scientific ...
- 867
3
votes
1
answer
492
views
Random non-intersecting circles in the plane
If I give a finite region of $\mathbb{R}^{2}$ and place $k$ circles of radius $r(k)$ uniformly at random inside, are there any known results for the probability that the circles do not overlap? ...
- 903
1
vote
1
answer
6k
views
Convert linear programming problem into its standard form [closed]
all,
I met a question that, the cost function of the linear programming problem is a function with absolute value. Here is the problem:
min 3x1+|6x2+3|
st.
|x1+4|+|2x2|<=3
How can I deal with it?...
- 13
2
votes
0
answers
118
views
Containing a "fuzzy" ellipsoid within an ordinary ellipsoid
Consider the ellipsoid described by the inequality $(x - x_c)^T P^{-1} (x - x_c) \leq 1$, where the vector $x_c \in \mathbb{R}^n$ denotes the center of the ellipsoid and the symmetric positive ...
1
vote
1
answer
1k
views
Linear programming with exponentially many constraints and variables [closed]
From class, I learnt that problems like traveller salesman have a Linear programming representation with exponentially many constraints. Using method of separation, this problem is solved rather ...
- 867
1
vote
2
answers
150
views
investigating positivity/negativity of a function [closed]
I'm investigating if and how the positivity or negativity of a multivariable function can be proved. Consider $y_{1},y_{2},y_{3}\in\mathbb{R}$ and the following function
$$f\left(y_{1},y_{2},y_{3}\...
- 23
5
votes
1
answer
393
views
Maximum number of general-position points with mutual rational distances?
Richard Guy has shown that there are six points in the plane—no three collinear,
no four cocircular—such that all interpoint distances are rational.
Guy, Richard. Unsolved Problems in ...
- 151k
8
votes
1
answer
1k
views
Dubins car shortest paths: Decidable?
A Dubins car follows a
Dubins path
in $\mathbb{R}^2$, with constant wheel speed and
limited turning radius.
It is known that the shortest Dubins path in the absence
of obstacles follows circular
arcs ...
- 151k
6
votes
4
answers
612
views
What can be said of the structure of a metric space without isosceles triangles?
This is a question that has been bothering me in the back of my head for quite some time.
Suppose we have a metric space $X$ with metric $\mathrm{d}$. By an isosceles triangle we mean a tuple of ...
- 526