All Questions
4,826 questions
3
votes
1
answer
132
views
How to maximize the variance of a subset of integers?
$\DeclareMathOperator{\Var}{Var}$Given the set of numbers $\Omega := \{1, \ldots, n\}, n \in \mathbb{Z}^+$, how can I choose a subset, $A$ of $\Omega$ , such that $\min(\Var(A), \Var(\Omega \setminus ...
- 1,372
0
votes
0
answers
32
views
Request for resources on directional derivative of the Riemannian distance function, and Berger's lemma about geodesics realizing the diameter
I've been recently interested in directional derivatives of the Riemannian distance function, and I came across this question, and its answer by Sergei Ivanov, where he stated an important result: (I ...
- 867
2
votes
1
answer
137
views
Does this result above six points follow have a name?
Does this result above six points follow have a name?
Let $A$, $B$, $C$, $D$, $E$, $F$ be six points in the plane and $AB, CF, ED$ are concurrent and $BC, DA, FE$ are concurrent then $CD, EB, AF$ ...
1
vote
0
answers
29
views
Integral hull of a polyhedron Q is polyhedron
Let $Q \subseteq R^n$ be a rational polyhedron and let $Q_I=Convexhull(Q \cap Z^n)$. By finite basis theorem, we have $Q=P+C$ for some rational polytope $P$ and finitely generated cone $C$ where $C=R_+...
- 21
2
votes
1
answer
202
views
To cut a triangle into $n$ $p$-sided polygonal regions
Given any triangular region and two integers $n$ and $p$ which can be large and $p > 4$. It is needed to cut the triangle into $n$ $p$-gons (e.g., cut a triangle into 10 heptagons). Among the $p$-...
- 5,979
20
votes
3
answers
1k
views
How can I randomly draw an ensemble of unit vectors that sum to zero?
Inspired by this question, I would like to determine the probability that a random knot of 6 unit sticks is a trefoil. This naturally leads to the following question:
Is there a way to sample ...
- 747
-1
votes
0
answers
41
views
Is it possible to backtrack an optimization solver? [closed]
I have an optimization problem and was using a linear programming optimizer to find solutions. However, I find that past a certain size, the problem becomes "infeasible" and has no solutions....
10
votes
1
answer
157
views
For what $n$ do there exist non-periodic tilings with rotational symmetry of order $n$?
More precisely, given an integer $n$, does there exist a non-periodic tiling, where there are infinitely many patches within the tiling, of indefinitely large area, with rotational symmetry of order $...
- 6,652
1
vote
2
answers
188
views
Non-compact surfaces with non-negative Gauss curvature
Is there a topological classification of non-compact complete connected 2-dimensional Riemannian manifolds with non-negative Gauss curvature?
- 641
2
votes
1
answer
877
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} &...
CommunityBot
- 1
16
votes
1
answer
3k
views
3-piece dissection of square to equilateral triangle?
At a workshop it was suggested that it likely remains an open problem
whether or not there is a 3- or 2 -piece
dissection
of a square to an equilateral triangle.
Can anyone confirm that this is ...
- 151k
-3
votes
0
answers
47
views
Proof AG = 2EF in an Isosceles Right Triangle [closed]
In an isosceles right triangle ABC with angle ACB = 90 degrees and angle CAB = angle ABC, let point G lie inside triangle ABC. In the isosceles right triangle CGE, where angle CGE = 90 degrees and CG =...
CommunityBot
- 1
0
votes
1
answer
90
views
How to calculate the maximum dimensions of a rectangle inside two concentric circles? [closed]
If I have a rectangle ABCD such that A and B touch two points of the outer circle and CD's touches one point of the inner circle, how could the maximum dimensions of the rectangle be calculated?
...
- 188k
10
votes
1
answer
673
views
A random variation on Pólya's orchard problem
Pólya's orchard problem is as follows:
"How thick must the
trunks of the trees in a regularly spaced circular orchard grow if they are
to block completely the view from the center?"
See, e....
- 105k
13
votes
3
answers
1k
views
Efficient visibility blockers in Pólya's orchard problem
Pólya's orchard problem asks for which radius $\rho$ of trees at each lattice point within a distance $R$ of the origin block all lines of sight to the exterior of the orchard.
It has been ...
- 105k
2
votes
0
answers
68
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 ...
- 105k
0
votes
2
answers
531
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} {\...
CommunityBot
- 1
2
votes
1
answer
61
views
$k$-subset with minimal Hausdorff distance to the whole set
Let $(\mathcal{M}, d)$ be a metric space. Let $k \in \mathbb{N}$. Let $[\mathcal{M}]^k$ be the set of $k$-subsets of $\mathcal{M}$. Consider the following problem:
$$ \operatorname*{argmin}_{\mathcal{...
CommunityBot
- 1
2
votes
0
answers
155
views
Inscribed square and convexity
Let $b(X)$ be the boundary of any $X$ subset of the plane.
Does there exist $A,B$ convex compact sets of the plane, such that $C:=A\setminus B$ is simply connected and not empty, and such that ...
8
votes
1
answer
422
views
Why $(\mathrm{Lip}([0,1]^2))^*$ is finitely representable in 1-Wasserstein space over the plane?
In "Snowflake universality of Wasserstein spaces"" by Alexandr Andoni, Assaf Naor, and Ofer Neiman, they have the following notation:
For a metric space X they write $\mathcal{P}_1(X)$ ...
CommunityBot
- 1
11
votes
1
answer
652
views
How to correctly state Cauchy's rigidity theorem?
Cauchy's rigidity theorem is often stated briefly as
Any two (convex, 3-dimensional) polyhedra with pairwise congruent faces are themselves congruent.
As a more formal generalization to general ...
- 13.6k
5
votes
1
answer
536
views
Twin circles in a quadrilateral
The circumcenters of the four triangles of a complete quadrilateral along with the two points of completion form two congruent circles (in black).
Surely this must've been done before - what's the ...
CommunityBot
- 1
1
vote
0
answers
67
views
Quasi-geodesics in Alexandrov spaces
I am trying to understand the notion of quasi-geodesic in Alexandrov space with curvature bounded below following the Perelman-Petrunin paper. I have two questions:
Is it true that the shortest ...
- 21.8k
0
votes
0
answers
21
views
Easy instance of set cover
I am trying to prove that a natural greedy algorithm solves the following instance of the set cover problem: for a set of elements $e\in U$ with a set of weights $w_e$, we define the cost of a subset ...
- 4,049
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 ...
CommunityBot
- 1
2
votes
1
answer
168
views
Ratio of inscribed/circumscribed ellipsoids: geometrical proof?
Let $K$ be a convex subset of ${\mathbb R}^n$, with non-void interior. The Löwner-John theorem states that there are a minimal volume ellipsoid $\cal E$ containing $K$, a maximal one $\cal F$ ...
- 1,538
0
votes
1
answer
231
views
Divide angles by coefficients relate to Fibonacci sequence
In the left Figure, consider a right triangle $OPA$ with $\angle {AOP} = 90^\circ$. Let $\ell$ be the reflection of $PO$ in $PA$ and $\ell$ meets $OA$ at $A_1$. Let $O_1$ be the center of the circle $(...
CommunityBot
- 1
1
vote
0
answers
37
views
Metric entropy of an ellipsoid
Let $B^d_2$ denote the unit ball of $\ell_2^d$ and let $T$ be an invertible linear map.
Consider the function
$$
H(T) := \log M(TB_2^d, B_2^d),
$$
which is the packing entropy for $TB_2^d$ by $B_2^d$....
- 380
11
votes
7
answers
1k
views
What are some interesting ways of making new metrics out of old metrics?
If $d(x,y)$ and $e(x,y)$ are metrics then $d(x,y)+e(x,y)$ and $\frac{d(x,y)}{1+d(x,y)}$ are metrics.
If $d_i(x,y)$ for $i=1,\dots,n$ are metrics then so is $\sqrt{\sum_{i=1}^n{d_i^2(x,y)}}$
Are ...
- 132
9
votes
0
answers
144
views
Which polytopes have compact realization spaces?
Let $P\subset\Bbb R^d$ be a convex polytope.
Its reduced realization space is the space of all combinatorially equivalent polytopes modulo projective transformations.
I am interested in polytopes for ...
- 13.6k
9
votes
1
answer
429
views
Perturbing metrics with nonpositive curvature
Let $M$ be a compact $3$-dimensional manifold diffeomorphic to a ball. Suppose that $M$ has nonpositive (sectional) curvature and its boundary $\partial M$ is convex, or even that $M$ is a Riemannian ...
CommunityBot
- 1
7
votes
2
answers
242
views
Prove that $ n \leq d+1 $ under ordering constraints in $\mathbb{R}^d$
Let $x_1, \dotsc, x_n \in \mathbb{R}^d$ and $\theta_1, \dotsc, \theta_n \in \mathbb{R}^d$ be vectors such that for every $k \in [n]$, the following inequality holds:
$$
\langle x_k, \theta_k \rangle &...
- 109k
10
votes
3
answers
460
views
Do triple-linked graphs exist?
Lets say that a finite simple graph $G$ is (intrinsically) fully triple-linked if for each embedding of $G$ into $\Bbb R^3$ we can find three disjoint cycles $C_1,C_2,C_3\subset G$ whose embeddings ...
- 13.6k
2
votes
0
answers
152
views
Isoperimetric inequality for Kähler manifolds
I am interested in the following form of isoperimetric inequality for Kähler Manifolds (for example unit ball $B^n\subset \mathbb{C}^n$ with Bergman metric). It should say something like this: if $F$ ...
- 356
-1
votes
0
answers
64
views
Axes of symmetry and symmetry group of the tangent cone to an open, connected, convex subset of the Euclidean space
Given a closed convex set $K\subset \mathbb{R}^d$ and a point $x\in K$ the tangent cone to $K$ at $x$ is defined by
\begin{equation}
T_xK:=\overline{\{v\in \mathbb{R}^d: \exists \lambda \geq 0 \text{ ...
- 1,465
1
vote
0
answers
31
views
Cut locus of linear isometric action quotients
Given a compact group $G\leq \operatorname{O}(d)$ of linear isometries on $\mathbb R^d$, equip its quotient $\mathbb R^d/G$ with the canonical orbital metric.
I am curious about the following. Is ...
- 63.9k
6
votes
1
answer
604
views
When is the cut locus a finite tree?
Let $\Omega \subset \mathbf{R}^2$ be a bounded, simply connected domain, with a regular boundary, say of class $C^2$ at least. Let the cut locus $C$ of $\Omega$ be the set of points $x \in \Omega$ for ...
CommunityBot
- 1
7
votes
2
answers
529
views
What is the name for a point that is periodic to within $\varepsilon$?
Let $X$ be a set and $f: X \to X$ a function. A point $x \in X$ is, of course, said to be periodic for $f$ if $x \in \{f(x), f^2(x), \ldots\}$.
Now suppose that $X$ is a topological space and $f$ is ...
- 5,407
0
votes
0
answers
72
views
Reflections of Voronoi diagrams
I wonder if something similar to the following fact is known, and I would greatly appreciate any references.
Let $t_1, t_2, \ldots, t_N$ be unit vectors in $\mathbb{R}^n$.
Let $S$ denote the unit ...
- 1
2
votes
1
answer
108
views
Discrete isoperimetric inequality involving the diameter of an n-gon
I am interested in discrete isoperimetric-type inequalities that allow one to bound the perimeter of an $n$-gon from above (as opposed to below, as in the classical case when one bounds the perimeter ...
- 1,625
2
votes
1
answer
312
views
Question on a vector inequality
Is it true that
$$
\min\left( \begin{aligned}
&\|\mathbf{u}\| + \|\mathbf{v}\| - \|\mathbf{u} + \mathbf{v}\|, \\
&\|\mathbf{u}\| + \|\mathbf{w}\| - \|\mathbf{u} + \mathbf{w}\|, \\
&\|\...
- 63.9k
0
votes
1
answer
67
views
Metric for measuring linearity of finite set of points in $R^2$
Suppose one has $n > 2$ points in $R^2$, and one wants to measure "how linear" they are.
I want a metric such that (a) if all the points are in fact on the same line, the metric gives 1, (...
- 63.9k
1
vote
1
answer
182
views
Metric currents on singular measures in $\mathbb R^d$
Unless I am misunderstanding a lot of works, it is my understanding that a finite and non negative measure $\mu=g\mathcal{H}^\alpha$, where $\mathcal{H}^\alpha$ is the $\alpha$-Haudorff measure, ...
0
votes
0
answers
42
views
Reference request: in Alexandrov geometry gradient flows preserve extremal subsets
It is mentioned in literature that in Alexandrov geometry gradient flows of semi-concave functions preserve each extremal subset.
I am looking for a proof of this fact.
- 21.8k
2
votes
0
answers
50
views
Riemannian metrics realizable as hypersurfaces both in Euclidean and spherical spaces
I am interested in smooth Riemannian metrics on $n$-sphere, $n\geq 3$, which can be imbedded isometrically both to $n+1$-dimensional Euclidean space and $n+1$-dimensional standard sphere of radius $r$....
- 21.8k
5
votes
1
answer
162
views
I believe that all facets of a Voronoi-cell of a lattice are centerally symmetric. Is my argument correct? Is this true?
So let $L$ be a full dimensional lattice in $\mathbb{R}^{n}$. Then the Voronoi-cell of the lattice are precisely the points in $\mathbb{R}^{n}$ that are at least as close to the origin, as to any ...
- 63.9k
4
votes
1
answer
174
views
Explicitly computing the absolutely minimising Lipschitz extension
Is there an analytical or even numerical way to find the Absolutely Minimizing Lipschitz extension of a given function?
I know that the extension exist and it is unique (by Aronsson et al).
I found ...
- 6,155
1
vote
1
answer
118
views
Contraction and consensus on Hadamard manifolds
Let $\mathcal M$ be a Hadamard manifold and $\{x_i\}_{i=1}^n\subseteq{\cal M}$ be $n$ points. Define $\{y_i\}_{i=1}^n$ as the weighted Fréchet means:
$$
y_i=\arg\min_{y\in\mathcal M}\sum_jw_{ij}d^2(y,...
CommunityBot
- 1
17
votes
2
answers
2k
views
Efficiently determine if convex hull contains the unit ball
Given a set of $n$ points in $\mathbb{R}^d$, is there an algorithm to determine if the convex hull contains the unit ball centered at the origin in polynomial time (in both $n$ and $d$)? The convex ...
- 221
6
votes
1
answer
413
views
How many unit cubes are needed to 'hide' a unit cube fully in 3D?
Question: What is the smallest number of nonoverlapping unit cubes that can hide a unit cube C - in the sense that every ray emanating from the boundary of C meets the interior or the boundary of one ...
- 506