All Questions
4,827 questions
9
votes
1
answer
6k
views
Proving that a binary matrix is totally unimodular
I'm working on a set of problems for which I can formulate binary integer programs. When I solve the linear relaxations of these problems, I always get integer solutions. I would like to prove that ...
- 213
18
votes
12
answers
10k
views
Theorems in Euclidean geometry with attractive proofs using more advanced methods
The butterfly theorem is notoriously tricky to prove using only "high-school geometry" but it can be proved elegantly once you think in terms of projective geometry, as explained in Ruelle's book The ...
49
votes
5
answers
5k
views
Is Lebesgue's "universal covering" problem still open?
The following problem has been attributed to Lebesgue. Let "set" denote any subset of the Euclidean plane. What is the greatest lower bound of the diameter of any set which contains a subset congruent ...
- 6,215
9
votes
1
answer
1k
views
Smallest dilation of a quadrilateral?
What is the smallest dilation of a quadrilateral in $\mathbb{R}^d$?
This may be an open problem;
my question is: Is this indeed open?
It will take me some time to explain the terms.
The notion of ...
- 151k
70
votes
4
answers
11k
views
$C^1$ isometric embedding of flat torus into $\mathbb{R}^3$
I read (in a paper by Emil Saucan) that the flat torus may be isometrically embedded
in $\mathbb{R}^3$ with a $C^1$ map by the Kuiper extension of the Nash Embedding Theorem,
a claim repeated in this ...
- 151k
12
votes
1
answer
1k
views
Fixed point theorems and equiangular lines
I've been thinking about the equiangular lines (or SIC-POVM) conjecture, and my conclusion is that the best means of attack would be through some kind of fixed point theorem -- I'm thinking ...
- 6,342
4
votes
1
answer
496
views
Is there a standard measure for how close a matrix is to being a distance metric ?
Suppose I have a square n*n, symmetric matrix with positive elements and zero diagonal.
For this to be considered a proper distance metric between n points, the triangle inequality needs to be ...
- 711
3
votes
0
answers
559
views
Unprovability of the Steiner-Lehmus theorem
Conway postulated that the Steiner-Lehmus theorem is unprovable using direct methods of proof. Can this be proven directly, that the Steiner-Lehmus theorem cannot be proven directly over Euclidean ...
- 131
5
votes
3
answers
1k
views
computability and geometry
Hello,
I am looking for a discussion on computability and algorithms in relation to geometric constructions.
Does anyone know if the subject has been treated from the viewpoint of elementary ...
- 59
2
votes
1
answer
518
views
When can a folded polygon be isometrically (locally) embedded into R^3?
I am interested in 3-D representations of various things that naturally live in a non-simply-connected compact surface. There is the usual way of producing a compact surface of any orientable or non-...
- 935
10
votes
3
answers
6k
views
Solving a system of linear inequalities -- what is the dimension of the solution set?
It is well known how to solve a system of linear equations $A{\bf x} = {\bf b}$, but how do we solve a system of linear inequalities $A{\bf x} \leq {\bf b}$?
For the applications I have in mind the ...
- 7,857
38
votes
3
answers
4k
views
Parabolic envelope of fireworks
The envelope of parabolic trajectories from a common launch point is itself a parabola.
In the U.S. soon many will have a chance to observe this fact directly, as the 4th of July is traditionally ...
- 151k
15
votes
1
answer
11k
views
Maximum number of mutually equidistant points in an n-dimensional Euclidean space is (n+1). Proof? [closed]
How to prove that the maximum number of mutually equidistant points in an n-dimensional Euclidean space is (n+1)?
- 191
6
votes
2
answers
8k
views
Existence/Uniqueness of Nonnegative Solutions of Linear Systems of Equations
Suppose we have an $m$x$n$ matrix $A$, with $m\lt n$, and an $m$x$1$ vector $b$. Are there existence and uniqueness conditions characterizing nonnegative solutions of the system of linear equations $...
9
votes
2
answers
674
views
Small crown probabilities (and infinite dimensional margin assumption)
My question is:
How do I find sharp upper bounds on $P(|q|\leq \epsilon)$ uniformly over a set of gaussian polynomes $q$ of degree two.
Notations and definitions (to make the question rigorous)
Let ...
13
votes
4
answers
1k
views
When sticks fall, will they weave?
Imagine $n$ $z$-vertical sticks uniformly spaced around a unit-radius circle in the $xy$-plane.
At $t{=}0$, each is randomly $\epsilon$-perturbed from the vertical, and they fall under
the influence ...
- 151k
4
votes
2
answers
2k
views
How can I efficiently determine which side of a line segment is internal to the polygon?
As part of a larger analysis I have a need to break a polygon into it's individual line segments and mark which side is "inside" of the polygon. If your curious this is going to be fed into a big ...
1
vote
0
answers
335
views
Irrationality of square root of 2 [closed]
It is possible to explain me the 18th proof of the irrationality of square root of 2 from the following site?
http://www.cut-the-knot.org/proofs/sq_root.shtml
- 27
15
votes
3
answers
1k
views
covering a square with unit squares
Can some square of side length greater than $n$ be covered by $n^2+1$ unit squares? (The unit squares may be rotated. The large square and its interior must be covered.)
- 897
4
votes
1
answer
1k
views
Finding integer points on an N-d convex hull
Suppose we have a convex hull computed as the solution to a linear programming problem (via whatever method you want). Given this convex hull (and the inequalities that formed the convex hull) is ...
- 1,801
61
votes
11
answers
11k
views
Geometric proof of the Vandermonde determinant?
The Vandermonde matrix is the $n\times n$ matrix whose $(i,j)$-th component is $x_j^{i-1}$, where the $x_j$ are indeterminates. It is well known that the determinant of this matrix is $$\prod_{1\leq ...
- 23k
1
vote
0
answers
578
views
Cluster-preserving and distance-maximizing embedding into Hamming Space?
I have a set of data, each instance in the real $[0,1]^{d}$. However, it's actually all in a relatively small range around 0.5, clustered into classes in even smaller ranges. The actual origin of the ...
- 2,383
26
votes
3
answers
11k
views
L1 distance between gaussian measures
L1 distance between gaussian measures: Definition
Let $P_1$ and $P_0$ be two gaussian measures on $\mathbb{R}^p$ with respective "mean,Variance" $m_1,C_1$ and $m_0,C_0$ (I assume matrices have full ...
- 833
94
votes
2
answers
6k
views
Volumes of sets of constant width in high dimensions
Background
The $n$-dimensional Euclidean ball of radius $1/2$ has width $1$ in every direction. Namely, when you consider a pair of parallel tangent hyperplanes in any direction the distance between ...
- 24.7k
16
votes
5
answers
1k
views
A characterization of convexity
While doing some research on polytopes I came to the following question. Maybe it's already somewhere but anyway I'll post it here.
Let $X\subset \mathbb{R}^3$ be such that, for every plane $P$, $P\...
- 1,001
9
votes
2
answers
3k
views
An optimization problem for points on the sphere (master's dissertation)
First, by means of a disclaimer, some background. I am entering the fourth and final year of an undergraduate master's degree in maths, and a quarter of the maximum credit for this year will be for a ...
- 3,612
6
votes
2
answers
1k
views
Minimum spanning tree of a weighted graph
I have a connected graph $G=(V,E)$ in $n$ vertices. The edge weights are non-negative and form a metric space, thus for vertices $u,v,w \in V$ , such that $(u,v), (v,w), (w,u)\in E$ we have $r(u,w) \...
- 89
55
votes
6
answers
8k
views
Is it possible to partition $\mathbb R^3$ into unit circles?
Is it possible to partition $\mathbb R^3$ into unit circles?
- 1,414
3
votes
1
answer
152
views
Defining a family of rotations with certain properties
Let $d \ge 2$, and consider the sphere $S^{d-1}$ embedded in $\mathbb R^d$. Does there exist a family of rotations $\{\mathcal O_v\}_{v \in S^{d-1}}$ which satisfies:
$\mathcal O_v e_1 = v$, and
$\...
- 8,512
6
votes
0
answers
176
views
Spaces with the thin tetrahedra property
I read a comment about the $\delta$-thin tetrahedra property of a space.
It basically means, that if you choose any four points in this space, connect them by geodesics, and fill each triangle with a ...
- 11.1k
8
votes
2
answers
741
views
Lattice Stick Number vs. Stick Number of Knot
Can the lattice stick number of a knot be bounded
by the stick number of the knot?
The stick number
$S(K)$ of a knot $K$ is the fewest number of segments
needed to realize it by a simple 3D polygon....
- 151k
4
votes
1
answer
866
views
When is a triangular matrix totally unimodular?
I have a {0,1}, invertible, triangular matrix, that I would like to show is totally unimodular. Are there any known results on the total unimodularity of classes of triangular matrices?
- 1,182
5
votes
1
answer
271
views
Feasibility of linear programs
It's known that finding the intersection of n halfplanes in 2-d takes $\Omega(n\log n)$ time. Does the lower bound apply if we change the question to deciding whether the intersection is non-empty?
- 201
23
votes
4
answers
5k
views
De Rham decomposition theorem, generalisations and good references
De Rham decomposition theorem states that every simply-connected Riemannian manifold $M$
that admits complementary sub-bundles $T'(M)$ and $T''(M)$ of its tangent bundle parallel with respect to the ...
- 28.9k
2
votes
2
answers
215
views
Is this a correct interpretation of support in coarse geometry?
Let $X = \mathbb{R}^n$, and consider a nondegenerate representation $\rho: C_0(X) \to B(H)$ where $B(H)$ is the algebra of bounded operators on a separable Hilbert space. The support of a vector $v \...
- 29.2k
8
votes
2
answers
621
views
Generalization of Hamiltonian cycles to "Hamiltonian spheres"
One possible generalization of a Hamiltonian cycle in a triangulated plane graph is what could be
called a Hamiltonian sphere: a collection of triangles within a simplicial complex in $\mathbb{R}^3$
...
- 151k
8
votes
2
answers
577
views
Coiling Rope in a Box: Decidable?
Is the problem Coiling Rope in a Box decidable? To be specific, is this decidable?
Given $L > 0$ and $r \in (0,\frac{1}{2})$,
both rational,
can a rope of length $L$ and radius $r$
fit ...
- 151k
2
votes
0
answers
5k
views
A system of linear equations with linear constraints
Mathematical problem.
Suppose we have $2n$ indeterminates $x_1,\dots,x_n$ and $y_1,\dots,y_n$ (which are denoted by $q$ with indices and called abundances below) and $m$ subsets $P_1,\dots,P_m$ of $\...
5
votes
1
answer
1k
views
Hyperbolic structure on surfaces with boundary
I have following two questions
1) Let $S$ be a compact oriented surface with (non-empty) boundary. Also assume that the Euler characteristic of $S$ is negative (Thus, $S$ is not disk or annulus). ...
- 439
14
votes
1
answer
587
views
Pushing convex bodies together
Given two convex bodies $A$ and $B$, in $\mathbb R^3$ let's say. We define $A(t)$ and $B(t)$ as $A+xt$ and $B+yt$ where $x,y$ are two arbitrary points. (That is the Minkowski sum, so the two bodies ...
- 85.6k
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
0
votes
2
answers
176
views
Polygon Chain - Conversion to non-crossing while preserving shape?
I have polygon chains similar to the following...
http://upload.wikimedia.org/wikipedia/commons/thumb/6/62/Self_crossed_polygonal_chain.svg/220px-Self_crossed_polygonal_chain.svg.png
...given the ...
- 1
4
votes
3
answers
1k
views
Unit triangles with vertices on circles
Characterize all triples $c_1,c_2,c_3$ of circles in the plane such that
there are infinitely many unit regular triangles $a_1a_2a_3$ with $a_i\in c_i$ for $i=1,2,3$.
In particular, are there any ...
- 1,359
21
votes
1
answer
2k
views
Coiling Rope in a Box
What is the longest rope length L of radius r that can fit into a box?
The rope is a smooth curve with a tubular
neighborhood of radius r, such that the rope does not
self-penetrate. For an open ...
- 151k
8
votes
2
answers
425
views
Are there arbitrarily sparse "lattices" in negatively curved symmetric spaces?
Let $X$ be a negatively curved symmetric space. In other words, $X$ is one of the four examples: a hyperbolic space, a complex hyperbolic space, a quaternionic hyperbolic space or the hyperbolic ...
- 32.4k
10
votes
0
answers
1k
views
Dissecting trapezoids into triangles of equal area
[Lightly edited for copy and proper formatting of mathematics. -- Pete L. Clark]
The Background: Let $T$ be a trapezoid. Sherman Stein, using valuation theory, showed that if $T$ is dissectible into ...
- 5,422
34
votes
3
answers
3k
views
What is the best way to peel fruit?
A mango made me wonder about this. (See also this question, which is in a similar spirit.)
Fix $L >0$ and a smooth body (possibly nonconvex—pears or bananas are fair game!) $B \subset \mathbb{R}^3$...
- 15.4k
4
votes
4
answers
7k
views
How to pick a random direction in n-dimensional space
I want to pick a random direction in n-dimensional space. How can I do this?
The reason I want to do this is to pick a neighbor for hill climbing optimization.
- 151
8
votes
1
answer
398
views
Möbius-invariant triangle center?
Given any two points x and y on a circle O, one can form four different lenses (regions between two circles, one of which is O) that have corners at x and y and make angles of 2π/3 at their corners. ...
- 18.6k
14
votes
5
answers
3k
views
Shortest-path Distances Determining the Metric?
The metric of a Riemannian manifold determines the shortest
distance between any two points.
I assume the reverse holds? That is, if you are given the
shortest distance d(x,y) between every pair of ...
- 151k