All Questions
Tagged with mg.metric-geometry discrete-geometry
671 questions
4
votes
2
answers
2k
views
Breaking a rectangle into smaller rectangles with small diagonals
Say I am given a rectangle with dimensions $a \times b$ and an integer $n$. I'd like to break this rectangle into $n$ smaller rectangles $R_i$, and I'd like to make the maximum diagonal of any of ...
- 30.1k
2
votes
0
answers
415
views
Find the intersection between two convex hulls, in this specific case
We work over $\mathbb{R}^K$. Let $V$ be the set of vectors whose coordinates take values $0$ or $1$, or equivalently the corners of the unit cube $[0,1]^K$.
Let $d:\{0, \ldots, K\} \to \mathbb{R}_+$ ...
- 233
10
votes
2
answers
523
views
When does every point in a polytope lie along a chord between its edges?
Consider the 3-simplex, or tetrahedron, in 3-space. Regardless of the positions of the vertices, every point in the simplex lies on a chord between two non-adjacent edges of the simplex. Or, ...
- 6,210
1
vote
3
answers
535
views
Isometric imbedding of finite metric space into standards spaces [duplicate]
Is it true that any metric space consisting of $n$ points can be isometrically imbedded into $n-1$ dimensional Euclidean space? Hyperbolic space?
(For $n=3$ this is true.) If not, what are necessary/...
CommunityBot
- 1
3
votes
1
answer
364
views
On distances between points on the plane
Take a set of $2n$ points in the plane and assume that no open set of diameter $1$ contains more than $n$ of these points.
Question: can we pair up the points so that the distance between the points ...
CommunityBot
- 1
5
votes
2
answers
557
views
What are the applications of Voronoi diagrams in pure mathematics? [closed]
Voronoi diagrams have interesting mathematical properties and applications in algorithms and modeling. But what are its applications in pure mathematics? For example, what theorems can be proved using ...
- 378
20
votes
1
answer
591
views
Update to Shephard's "Twenty Problems on Convex Polyhedra"
Forty-three years ago, Geoffrey Shephard published an influential list of open problems
on convex polyhedra.
Progress has been made on several of his problems, and perhaps some have been completely ...
- 188k
8
votes
1
answer
417
views
Orthonormal bases of R^3 with components lying in the golden field
Greg Egan proved an interesting theorem about unit vectors in $\mathbb{R}^3$ whose components actually lie in the 'golden field' $\mathbb{Q}[\sqrt{5}]$. He found it in our studies of twin dodecahedra:...
- 2,902
12
votes
2
answers
5k
views
The Gauss circle problem on a hexagonal lattice
Take an infinite hexagonal lattice (or equivalently, an equilateral triangular lattice), with unit spacing between the closest lattice point pairs, and draw a disc of radius $r$ centered on a lattice ...
- 1,018
3
votes
0
answers
169
views
Computing Voronoi poles in $\mathbb{R}^d$ (the farthest points within each cell)
Say I have a Voronoi diagram of some points $p_1,\dots,p_n\in\mathbb{R}^d$, which tesselates $\mathbb{R}^d$ into cells $V_1,\dots,V_n$. Within each cell $V_i$, the pole is defined as the vertex of $...
- 6,210
5
votes
2
answers
1k
views
regular polyhedra (and polytopes) in hyperbolic geometry, and generalisations
While there exist regular tesselations of the hyperbolic plane with arbitrary regular polygons, there are no new regular polyhedra in hyperbolic (3D) space. This being quite trivial, it is probably ...
- 151k
10
votes
1
answer
300
views
Optimal shape for stabbing balls in $\mathbb{R}^3$
I have radius $r < \frac{1}{2}$ congruent balls with centers randomly distributed uniformly within a region,
say, within a unit-radius sphere $S$.
I shoot a ray/path through $S$, hoping to ...
- 28k
11
votes
1
answer
807
views
Soft question: mathematics about truchet tiles
It seems that this is the first question on Truchet tiles on MO.
Shown above is a picture of a random tile, which you can see the resulting configuration is much like many membranes of cells.
I ...
- 356
3
votes
1
answer
518
views
n-dimensional Delaunay Triangulation of Lattices
I have several questions concerning the Delaunay triangulation of a high dimensional lattice.
Given an $n$-dimensional lattice $L$ and its Delaunay triangulation (partition of $R^n$ into simplices ...
- 1,502
1
vote
0
answers
70
views
Covering number of the range of a function
I have come across the need to know a bound on a certain curious quantity: the covering number of the range of a continuous function $f: D \rightarrow \mathbb{R}^n$, where $D \subseteq \mathbb{R}^m$. ...
- 183
6
votes
1
answer
2k
views
Given a set of 2D vertices, how to create a minimum-area polygon which contains all the given vertices?
Not sure whether this question belongs here or math.stackexchange.
You can assume that all the vertices are unique. The given vertices can be the vertices of the polygon, thus they do NOT have to be ...
- 6,210
17
votes
1
answer
390
views
4
votes
1
answer
367
views
convex polyhedron in the unit cube
Let $P$ be a given finite set of points within the $n$-dimensional unit cube. A finite set $Q$ of points within the $n$-dimensional unit cube covers $P$ if $\operatorname{conv}(Q) \supseteq P$ where $\...
- 6,210
2
votes
0
answers
2k
views
Find m most distant points from a set of n points [closed]
I would like to find the $m$ (where $n$ $\geq$ $m$ > 1) maximally distant subset of points from a collection of $n$ $d$-dimensional points. Maximally distant means the sum of the pairwise distances ...
CommunityBot
- 1
17
votes
0
answers
488
views
Large almost equilateral sets in finite-dimensional Banach spaces
Question: Does there exist a function $C:~(0,1)\to
(0,\infty)$ such that for each $\varepsilon\in(0,1)$ every Banach space
$X$ of dimension $\ge C(\varepsilon)\log n$ contains an $n$-point
set $\{x_i\...
- 4,878
2
votes
2
answers
5k
views
Best fit for multiple shapes inside an area
Is there a forumla to come up with the best fit for multiple shapes inside a rectangular area, so that none of the shapes are overlapping?
CommunityBot
- 1
9
votes
1
answer
665
views
Question about tetrahedron decomposition
Are there tetrahedra which can be subdivided into three non-overlapping parts similar to the original? I believe this would require splitting one face into three parts. I know some types of tetrahedra ...
- 6,210
2
votes
1
answer
115
views
Covering the annulus of d-cube
Given a convex body $C\subset R^d$ and a positive real $\lambda$, any set of the form $\lambda C + x = \{ \lambda c+x \mid c\in C \}$, for some $x\in R^d$, is called a homothetic copy of $C$. The ...
- 6,210
1
vote
1
answer
524
views
How to compute the number of regular spheres needed to fill a rectangular space
Computing the volume of a sphere is straightforward 4/3*pi*R^3
As is the volume of a rectangular space length*width*height (e.g. 10*10*6)
How might I go about determining how many spheres would fit ...
CommunityBot
- 1
5
votes
1
answer
307
views
Panning for gold nuggets: a type of isoperimetric problem
Let $C$ be a unit-radius circle in the plane.
Suppose you have a total length $L$ of string available, and
your task is to connect chords of $C$ using no more
than $L$ of string to minimize the ...
CommunityBot
- 1
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_{\...
CommunityBot
- 1
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
6
votes
2
answers
268
views
Counting valid coordinates
We are given a matrix $D = (d(i,j))_{1 \leq i,j \leq n}$ such that $d(x,z) \leq d(x,y) + d(y,z)$ for each $1 \leq x,y,z \leq n$. It is also known that $d(x,y) \in \mathbb{N}$ (In this question $0 \in \...
CommunityBot
- 1
6
votes
3
answers
1k
views
Consecutive Integer Squared Square
Is it possible to construct a squared square out of consecutive integer squares?
Be it 1,2,3,...n or k,k+1,k+2,...n.
- 480
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 ...
- 6,101
2
votes
1
answer
88
views
Visibility kernels of embedded graphs
Let $G$ be a connected graph embedded in the plane with all edges straight segments.
For $\alpha \in (0,\pi)$, define an $\alpha$-path as a path in $G$ with
all turns at vertices within $[-\alpha,\...
- 23.7k
3
votes
1
answer
439
views
Convex n-polytope general position vectors to general position vectors of tetrahedron
I asked this question in a comment to this question, but got no response. I thought that perhaps it needed more exposure, so I made it a question in itself.
Define a set of general position vectors $...
CommunityBot
- 1
19
votes
2
answers
1k
views
Four Dimensional Origami Axioms
What are the axioms of four dimensional Origami.
If standard Origami is considered three dimensional, it has points, lines, surfaces and folds to create a three dimensional form from the folded ...
CommunityBot
- 1
3
votes
0
answers
122
views
A taut string of equilateral triangles
Let $T$ be a unit edge-length equilateral triangle composed of three cylinders each
of (small) radius $r>0$. (By "small" I mean approximately $< 0.1$.)
Think of $T$ as a physical, rigid triangle,...
- 151k
11
votes
4
answers
608
views
What is the right way to think about / represent general tilings?
For periodic/symmetric tilings, it seems somewhat "obvious" to me that it just comes down to working out the right group of symmetries for each of the relevant shapes/tiles, but its not clear to me if ...
CommunityBot
- 1
3
votes
1
answer
349
views
Covering points with a shortest lattice spiral
Let $S$ be a finite set of lattice points in $\mathbb{Z}^2$.
My question is, roughly:
Q. How can a shortest lattice spiral that passes through
every point of $S$ be found?
A lattice spiral (my ...
- 151k
9
votes
1
answer
370
views
Largest convex hull of a unit length path
What is the largest area possible for the convex hull of a path of unit length lying on a plane? For what paths is that largest area attained?
- 13.4k
7
votes
1
answer
137
views
Dropping altitudes to achieve nonobtuse planar triangulations: finite or infinite?
Given a planar triangulation of (say) a convex region,
imagine the following process to convert it to a triangulation with
no obtuse angles:
Pick an arbitrary obtuse angle at vertex $a$ of $\triangle ...
- 628
2
votes
1
answer
118
views
Characterization of the medial axis of a surface
I would like to know if the following "characterization" of the medial axis of a surface is correct, and if so, how to prove it.
Let $S$ be a continuous, piecewise smooth, compact surface embedded in ...
- 151k
24
votes
3
answers
3k
views
Can a unit square be cut into rectangles that tile a rectangle with irrational sides?
For arbitrary positive integers $m$ and $n$, if we dissect a unit square into an $m\times n$ rectangular grid of $1/m\times 1/n$ rectangles, we can reassemble these $mn$ rectangles into an $n/m\times ...
- 2,933
6
votes
1
answer
205
views
Hiding $k$ disks inside a larger disk
Suppose one has $k$ unit-radius disks, and the goal is to hide them inside
a disk of radius $R \gg k$.
The detection probes are rays along a line.
(Think of the disks as tumor cells, and the rays as ...
- 6,101
3
votes
1
answer
1k
views
Bound on maximum distance between points on a unit N-Sphere
I want to select M points on the N-sphere such that $min_{i\neq j,i,j\in \{1..M\}} ||x_i - x_j||$ is maximized.
Are there good upper bounds for this max-min distance?
- 96.4k
4
votes
1
answer
258
views
The Mahler conjecture and non-zonoidal 3-polytopes (4-polytopes)
I have been working on the Mahler conjecture for over a year now and have made some progress for certain classes of convex polytopes and I'm now attempting to write up my results specified to $\mathbb{...
- 1,312
1
vote
1
answer
57
views
Maximum crossings of curvature-constrained curve
Let $C$ be a curve in the plane whose curvature is everywhere $\le 1$.
If $C$ has length $L$, what is the largest number of proper self-crossings
of $C$ as a function of $L$?
For example, the curve ...
- 20.2k
2
votes
0
answers
112
views
What is the projective dual of a planar graph?
Everybody learns the usual definition of the dual of a planar graph when edges are preserved and faces are mapped to vertices. Everybody learns the projective duality. What if we apply it to a ...
- 19k
7
votes
1
answer
439
views
Integral straight-line embeddings of planar graphs
Wikipedia says (in the article on Fáry's theorem),
"Heiko Harborth raised the question of whether every planar graph has a straight line representation in which all edge lengths are integers. The ...
- 18.6k
1
vote
0
answers
80
views
Euclidean embedding of a graph based on 1-ring neighborhood distances only
Consider a graph $(V,E)$, $\vert V \vert = n$ and weights $\{l_{ij}\}$, where $l_{ij}>0$ iff there is an edge connecting vertices $v_i$ and $v_j$. Distances beyond the 1-ring neighborhood are not ...
- 337
2
votes
1
answer
133
views
Omit each vertex in turn of convex polygon: Iterative limit?
Let $P=P_0$ be a convex polygon of $n$ vertices $v_k$.
Let $P_{i+1}$ be the convex polygon obtained by intersecting the halfplanes
determined by the lines through every other vertex.
Below, $P_0$ is ...
- 8,903