5
votes
1answer
263 views
+50

Separating points in the plane II

Let A be a set of $2m$ points on the plane so that no open set of diameter $2$ has more than m of them. Define $A+A+...+A$ ($k$ times) to be the multiset of $k$-sums from $A$. That is, we consider all ...
7
votes
2answers
116 views

Trees with a maximal convex hull: are the only optimal solutions Steiner trees?

For given $n\geqslant 3$, I'm looking for a connected set composed of $n$ equal segments in the plane such that the convex hull of it has maximal area $A(n)$. To simplify notation, we'll take ...
4
votes
2answers
100 views

Which criteria guarantee an orthogonal circuit in $\mathbb R^3$ to be rigid?

For $n\ge4$, define an orthogonal circuit or O-circuit as a closed circuit of $n$ unit segments in $\mathbb R^3$ such that any two neighboring segments form a right angle. (Physically this could be ...
7
votes
0answers
229 views

diameter as a Morse function

Consider the space $X_1$ of closed subsets not containing a pair of antipodal points of the unit circle. Here we have a kind of degenerate Morse function, defined by the diameter of the pointset. ...
4
votes
2answers
315 views

A question about pairs of lines in 3D projective space

Consider a 3-dimensional projective space $X$. Let $m$ be the smallest number so that there are $m$ pairs of lines $ \ell_1,\ell'_1$, $ \ell_2,\ell_2'$, ... , $\ell_m, \ell'_m$ in $X$: a) For ...
9
votes
3answers
760 views

Could a perfect squared square be split into two perfect squared squares?

This is a geometric puzzle though it might conceivably also define a special class of Pythagorean triples. A perfect squared square PSS is a square (as a plane figure) partitioned into smaller ...
6
votes
1answer
101 views

Maximizing ratio volume/diameter^n by an affinity

Suppose we have a convex compact body $D\subset \mathbb R^n$. We can try to apply affine transformation keeping the volume and decreasing the diameter of $D$. It is clear that there is a constant ...
10
votes
1answer
301 views

Tverberg's theorem in CAT(0) spaces

Does Tverberg's theorem hold for CAT(0) spaces of covering dimension $d<\infty$: Is it true that for any $d$-dimensional $CAT(0)$-space $X$ and a subset $E\subset X$ of cardinality $(d + 1)(r - ...
12
votes
0answers
132 views

realization spaces of 3-dimensional polytopes

It is a well-know result (Steinitz, 1922) that the realization space of 3-dimensional convex polytopes with fixed combinatorics is contractible. A proof of this theorem can be found for instance in ...
6
votes
1answer
446 views

Separating pairs of points in R^n

Let $A$ be a set of $2k$ points in $\mathbb{R}^n$ such that no open set in $\mathbb{R}^n$ of diameter $2$ contains more than $k$ of these points. What is the largest possible distance $r_n>0$ one ...
7
votes
0answers
189 views

Right-angled polytopes

%This question is motivated by the little discussion here at the bottom. The following thing are known about hyperbolic right-angled polytopes: Compact hyperbolic right-angled polytopes do not ...
12
votes
2answers
442 views

Sets of evenly distributed points in the Euclidean plane

Is there a set $P \subset \mathbb{R}^2$ of points in the Euclidean plane whose intersection with every convex subset of $\mathbb{R}^2$ of area $1$ is nonempty but finite? If the answer is yes, can ...
3
votes
0answers
97 views

Generalized flag complex?

Assume we glue an $n$-dimensional simplicial complex $K$ from copies of an $n$-simplex $\Delta$ with fixed spherical metric. We may think that $\Delta$ has colored vertices and we glue so that the ...
3
votes
2answers
238 views

Problems similar to Borsuk’s Theorem in the plane

Consider a 2-dimensional Borsuk's theorem: Every bounded set $S$ in the plane can be partitioned into three parts with diameter smaller than the diameter of $S$. I wonder if there are any ...
10
votes
1answer
272 views

The number of relevant scales for a finite metric space

For an $n$-element metric space $X=\{x_1,\dots,x_n\}$ with metric $d$ we introduce an array containing $\frac{n(n-1)}2$ numbers $d(x_i,x_j)$, $i<j$. We assume that all distances are at least $1$. ...
1
vote
1answer
157 views

Pythagorean triples related to non-isometric equidistant plane quadruples

QUESTION   Do there exist integers   $u\ x\ A\ B$   such that   $x\ne 0$,   and the following two equalities hold: $ x^2 + (x-u)^2\ =\ A^2$ $ x^2 + (x+u)^2\ =\ B^2$ ? ...
9
votes
1answer
275 views

Maximum number of Vertices of Hypercube covered by Ball of radius R

Let $R>0$ be given and let $H^n$ be the unit hypercube in $\mathbb{R}^n$. The problem I am facing is to find the maximum number of vertices of $H^n$ which can be covered by a closed $n$-dimensional ...
4
votes
1answer
231 views

A regular polytope

For positive integers $m$ and $n$, consider a regular polytope in ${\mathbb R}^{m+n+mn}$ with $2^{m+n}$ vertices, corresponding to each $\sigma \in \{-1,1\}^{m+n}$ as follows. The first $m+n$ ...
7
votes
0answers
154 views

Minimal spanning tree of a point set in the unit square, under an unusual distance function

For two points $x$, $y \in [0,1]^2$, let their distance be $d(x,y) := \|x-y\|_2^2$ (i.e. the usual distance, squared). Technically, this is a semimetric, as it does not satisfy the triangle ...
5
votes
2answers
258 views

Kissing Number of Spheres in Non-Euclidean Geometry

There has been much work done on the kissing number problem (of determining the greatest number of congruent spheres which can touch a single sphere in a packing) in Euclidean space for dimensions $1$ ...
1
vote
1answer
421 views

Is this min not less than a min

Let $\mathbf{D}$ be the unit disk, is $$\inf_{\begin{array}{c} v_{1},v_{2},v_{3},v_{4}\in\mathbf{D},\\ v_{0}\in\mbox{convexhull}\left(v_{1},v_{2},v_{3},v_{4}\right) \end{array}}\max_{0\le ...
7
votes
0answers
284 views

Volume-like property to upper bound lattice points in a convex body

The following question arises in passing in a joint paper that I am working on. Let $K$ be a centrally symmetric convex body in an $n$-dimensional real vector space $V$ which contains a lattice $L$. ...
2
votes
2answers
227 views

What is the smallest number of subsets in such a subdivision?

Given any $30$ points in the plane, what is the smallest number of subsets in a subdivision of the set of $30$ points into subsets such that all the points in each subset are on the boundary of the ...
11
votes
1answer
349 views

Can all convex polytopes be realized with vertices on surface of convex body?

The following question was asked by me on Mathematics.SE. Unfortunately, no one answered it so I thought I might give it a try one level higher. Below the line you can find the slightly edited ...
1
vote
0answers
144 views

dissections and vertices of non-convex polytopes

Let us call a finite union $P$ of $n$-dimensional compact convex polytopes in $\mathbb{R}^n$ a non-convex polytope. Recall that a dissection of $P$ is a finite collection $T$ of $n$-dimensional ...
20
votes
1answer
1k views

A Weak Form of Borsuk's Conjecture

Problem: Let P be a d-dimensional polytope with n facets. Is it always true that P can be covered by n sets of smaller diameter? Background and motivation The Borsuk conjecture (disproved in ...
7
votes
4answers
528 views

Tessellating $\mathbb{R}^n$ by bricks.

Let us call the $\ell_1$-product of intervals $[0,k_1]\times...\times [0,k_n]$ a brick of size $k_1+...+k_n$. Consider a tessellation $T$ of $\mathbb{R^n}$ by (shifted) bricks so that every point ...
7
votes
1answer
579 views

Doubling dimension of a Euclidean space

The doubling dimension of a metric space $X$ is the smallest positive integer $k$ such that every ball of $X$ can be covered by $2^k$ balls of half the radius. It is well known that the doubling ...
17
votes
4answers
687 views

The Constructions of Davis and Januszkiewicz

One of the most useful tools in the study of convex polytope is to move from polytopes (through their fans) to toric varieties and see how properties of the associated toric variety reflects back on ...
26
votes
1answer
1k views

High-Dimensional Analogs of Polygon Spaces

[Edit: I had a mistake in the numerology (took d=6,5 instead of d=5,4). Edit: I mistakenly identified my mistake, it is 6,5 but I got the indices shifted by one.] Background: Polygon spaces Given a ...
14
votes
2answers
589 views

Random permutations from Brownian motion

Let $B(t)$ be a Brownian motion. The ordering of $(0, B(1), ..., B(n-1)) $ is a random permutation in $S_n$. This is not uniform for $n>2$ since the probabilities of the identity permutation ...
3
votes
3answers
238 views

measuring n 2-planes in R^{2n}.

Given $n$ vectors $v_1, \ldots, v_n$ in $\mathbb{R}^n$ of course we all know at least one measure for their relative configuration: $|v_1 \wedge\ldots \wedge v_n|$. Now suppose one were given $n$ ...
9
votes
3answers
718 views

Point sets in Euclidean space with a small number of distinct distances

It is well known and not hard to prove that the regular simplex in n-dimensions is the only way to place n+1 points so that the distance between distinct pairs of points is always the same. My general ...
12
votes
1answer
601 views

Applications of the GCD metric

In the pre-MO era, I once realized that on the integers, the function $$ d(m, n) := \sqrt{\log \frac{\sqrt{mn}} {\text{gcd}(m,n)}}\ , $$ is a metric (all properties are easily verified; in fact ...
4
votes
0answers
412 views

Intersection of pencils in $\mathcal{R}^2$

Consider $9n$ pencils through non-collinear points $p_1, \ldots , p_{9n}$ in $R^2$ each consisting of at most $n$ concurrent lines. Define the intersection $S$ of these pencils to be the set of points ...
7
votes
2answers
295 views

non-rigidity of interior points in polyhedral triangulations?

It's well-known that any compact polyhedron $P$ in $\mathbb{R}^n$ (we talk about piecewise-linear setting there, i.e. $P$ is a finite union of compact convex polytopes) can be triangulated into ...
4
votes
1answer
396 views

When can a 3-dimensional triangulation be isometricaly embedded in R^n?

Consider a triangulation of some bounded region of $R^3$ with a (finite) set of tetrahedra (like in Regge calculus). It can be thought of as a simplicial 3-complex with specified lengths of edges. The ...
1
vote
1answer
277 views

Large subgroups of the Hamming cube

Let's consider the abelian group $\mathbb{Z}^N_2$ equipped with the Hamming metric (the hypercube). Suppose I have a subgroup of this hypercube (not necessarily a subcube) which is generated by a set ...
7
votes
1answer
358 views

The volume of the “unit ball” in $\mathbb{R}^{m\times n}$ with respect to the cut norm

This question is inspired by the question “ε-nets with respect to the cut norm” by the user Aaron, which had been reposted to cstheory.stackexchange.com. The cut norm ||A||C of a matrix A=(aij)∈ℝm×n ...
13
votes
0answers
469 views

$\epsilon$-nets with respect to the cut norm

The cut norm $||A||\_C$ of a real matrix $A = (a_{i,j}) \in \mathcal{R}^{n\times n}$ is the maximum over all $I \subseteq [n], J \subseteq [n]$ of the quantity $\left|\sum_{i \in I, j \in ...
3
votes
0answers
195 views

How many set partitions on a big cube’s boundary arise from cubomino decompositions of the solid cube?

Introduction. This is a counting question about configurations that can appear on the outside of assembled Soma cube-like puzzles. More specifically, it’s about the ways in which the pieces of an ...
14
votes
3answers
1k views

Representation of vectors in $\mathbb{R}^2$ via differences of small vectors.

Is the following fact true? Let $v_1,\ldots, v_k \in \mathbb{R}^2$, $\|v_i\|\leq 1$, be vectors that add up to zero. Does there exist a permutation $\sigma\in S_k$ and vectors $w_1,\ldots, w_k ...
2
votes
4answers
189 views

How to compare finite point sets in normed spaces?

I want to define a "distance" between two subsets $A, B$ of a normed space $(V, \|\cdot\|)$ both with (at most) $n$ elements. A straightforward way for me to do this would be to define $$ d(A, B) := ...
2
votes
1answer
2k 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)?
5
votes
2answers
505 views

Maximal area coverable by $k$ disjoint isosceles triangles contained in a triangle of area 1.

Given a triangle $\Delta$ of unit area, how much area can always be covered by $k$ isosceles triangles contained in $\Delta$ and intersecting at most at their boundaries? The answer is easy for ...
11
votes
3answers
772 views

To what extent is convexity a local property?

A polyhedron is the intersection of a finite collection of halfspaces. These halfspaces are not assumed to be linear, i.e. their bounding hyperplanes are not assumed to contain the origin. The ...
20
votes
2answers
5k views

Is the Jaccard distance a distance?

Wikipedia defines the Jaccard distance between sets A and B as $$J_\delta(A,B)=1-\frac{|A\cap B|}{|A\cup B|}.$$ There's also a book claiming that this is a metric. However, I couldn't find any ...
5
votes
3answers
608 views

How can I embed an N-points metric space to a hypercube with low distortion?

I have a N-point metric space defined by the pairwise distance matrix. I want to encode these N points with binary strings, i.e. each point will be mapped to a vertex in a hypercube. The lengths of ...
12
votes
3answers
986 views

distance regular metric spaces

A metric space (V,d) will be called distance regular if for every distances a>0, b, c a nonnegative integer p(a,b,c) is defined, so that whenever d(B,C)=a, there are precisely p(a,b,c) points A ...
9
votes
1answer
517 views

Which changes of metric fix all open balls of a metric space?

In an earlier question, I was interested in counting the number of metric spaces on N points, where I considered two metric spaces to be the same if they had the same collection of open balls. Two ...