All Questions
Tagged with triangulations mg.metric-geometry
23 questions
6
votes
2
answers
404
views
Estimating shortest paths in planar drawings of graphs
Consider a drawing (in $\mathbb{R}^2$) of a planar graph. (The drawing is given, contrarily to the common setup in graph theory where we are seeking to build a drawing with specific properties.)
For ...
- 307
3
votes
0
answers
69
views
Volume of all Voronoi cells in n-dimensional bounded space
How can one find the volume of all Voronoi cells (bounded and unbounded) in an $n$-dimensional bounded space? For instance, consider an $N$-dimensional space (hypercube) with bounds on each dimension ...
- 131
0
votes
0
answers
125
views
Naming convention for different type of triangulations
When studying random geometries and related mathematical/physical stuff conflicting naming convention pops up regarding the naming of the different ensemble types of triangulations (in general ...
- 183
1
vote
0
answers
84
views
Number of polyhedral covers of a triangulation of $S^2$
For a given triangulation (combinatorial Type I. or Type II.) of a $2$-sphere, what is the number of unique polygonal covers with $n$ polygons where ($n$ goes from $2$ to $N$)?
Under polygonal cover, ...
- 183
5
votes
1
answer
223
views
Proof of Lemma 37.5 in Pak's Lectures on Discrete and Polyhedral Geometry
I am staring at the proof of Lemma 37.5 in Lectures on Discrete and Polyhedral Geometry, see page 331.
I cannot understand why the required triangulation exists.
In the first paragraph it says "...
- 14.3k
0
votes
1
answer
518
views
Distance between two points using triangulation
Suppose we have two points $p_1$ and $p_2$ in a metric space with unknown dimensionality, with no way to directly compute the distance between them, e.g. no coordinates.
Say we can randomly sample a ...
1
vote
0
answers
49
views
Influence of the degenerate Delaunay tiles on the Voronoï diagram
About three or four years ago, I implemented the Delaunay and Voronoi tessellations in Haskell, with the help of the Qhull C library. Now I reimplement it in R.
I have noticed that including or not ...
- 2,560
1
vote
1
answer
51
views
On triangulations and "coverage" of circumcircles
Let $P$ be a convex quadrilateral defined by four vertices $a$, $b$, $c$, and $d$. Suppose that the circumcircle of $\triangle abd$ contains $c$.* Let $D(\triangle abc)$ to denote the area enclosed by ...
- 173
5
votes
0
answers
214
views
Covering the sphere with an approximately planar grid
Consider a triangulation of a radius $R$ sphere into $n$ triangles. Must $Ω(\sqrt n)$ triangles have $Ω(1)$ relative difference from being an equilateral triangle of area $4πR^2/n$? ($Ω$ is from ...
- 7,545
15
votes
1
answer
616
views
Acute triangles in "obtuse" polygons?
Let $P$ be a convex polygon. Suppose every interior angle of $P$ is obtuse. Is it always the case that there exist three vertices $p, q, r$ of $P$ such that $\triangle pqr$ is acute?
I conjecture ...
- 173
10
votes
2
answers
751
views
On Gromov's proof of the systolic inequality $\operatorname{Sys}_1(M)\leq 6\operatorname{FillRad}(M)$
In the page 10 of the paper "Filling Riemannian manifolds" by Gromov (ProjetEuclid link), the author proves the following inequality (1.2) relating the systole and the filling radius of manifolds.
$$\...
- 469
9
votes
1
answer
281
views
Is every compact smooth Riemannian manifold bilipschitz equivalent to a finite simplicial complex?
Let $M$ be a compact smooth Riemannian manifold. Then it admits a triangulation, i.e. a finite simplicial complex $K$ which is homeomorphic to $M$. Any such simplicial complex carries a natural metric ...
- 91
3
votes
2
answers
323
views
Minimum weight triangulation of lattice points in a circle
Let $r$ be a natural number, and consider the $\mathbb{Z}^2$ lattice points
$S$ inside or on the circle $C$ of radius $r$ centered on the origin.
Let $P$ be the convex hull of $S$; so $P$ is inscribed ...
- 151k
6
votes
1
answer
228
views
Does this iterated Delaunay triangulation process always "explode"?
Let $P$ be a set of three noncollinear points in $\mathbb{R}^2$.
Iteratively form the
Delaunay triangulation
$\cal T$ of $P$, and then
augment $P$ by the circumcircle centers of all triangles in $\...
- 151k
2
votes
1
answer
183
views
Triangulations of translation surfaces whose edges are shorter than the diameter
Let $S$ be a compact translation surface (i.e. a surface endowed with a singular flat metric such that singular points are locally isometric to a cone of angle an integer multiple of $2\pi$, and that ...
- 2,696
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 ...
- 151k
4
votes
1
answer
323
views
What properties does generalized Delaunay triangulation have?
Suppose that instead of the usual circle, we pick some other convex set D and make the Delaunay triangulation of a finite planar point set with respect to this set, i.e. connect two points if there is ...
- 19.1k
5
votes
6
answers
435
views
Characterizing Convex Configurations of Quadrupels of Coplanar Points via Linear (In-)equalities between Distance Sums or Differences
Given 4 points $A$, $B$, $C$ and $D$ in general position in the euclidean plane, is it possible to determine from the 6 distances $AB$, $BC$, $CD$, $AD$, $AC$ and, $BD$ alone, whether every point is a ...
- 13.2k
8
votes
1
answer
358
views
Smoothing of piecewise Euclidean Riemannian metrics
Let $M$ be a smooth closed manifold and $T$ be a triangulation of $M$. Endow each simplex of $T$ with the Euclidean metric making it a regular simplex; this gives a piecewise Euclidean metric $g_0$ on ...
- 14.4k
2
votes
2
answers
722
views
Euclidean triangulation of the plane with degree 7 at each vertex.
Hyperbolic plane has a beautiful triangulation by congruent hyperbolic triangles where all the vertices of the triangulation have degree 7, this is of course not possible in the euclidean plane, even ...
- 1,101
1
vote
0
answers
247
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 ...
- 14k
29
votes
1
answer
2k
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 ...
- 24.7k
1
vote
1
answer
3k
views
3D Delaunay Triangulation -> Euclidean Minimum Spanning Tree
I read that the Euclidean Minimum Spanning Tree (EMST) of a set of points is a subgraph of any Delaunay triangulation. Apparently the easiest/fastest way to obtain the EMST is to find the Deluanay ...
- 171