Questions tagged [triangulations]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
5 votes
3 answers
224 views

Ideal triangulations of $3$-manifolds with "cusps" of genus $\ge 2$

Typically when one thinks about ideal triangulations of a $3$-manifold the link of each ideal vertex is a circle, so the ideal points correspond to toroidal cusps; alternatively, one can truncate the ...
Calvin McPhail-Snyder's user avatar
5 votes
2 answers
338 views

Does every triangulable manifold have a vertex-transitive triangulation?

Does every triangulable manifold have a vertex-transitive triangulation? When I talk about a vertex-transitive triangulation of a manifold, I mean in the sense of realizing a manifold homeomorphically ...
Mike's user avatar
  • 335
5 votes
6 answers
434 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 ...
Manfred Weis's user avatar
  • 12.6k
5 votes
1 answer
268 views

Is every triangulation of a Euclidean ball by convex tetrahedra shellable?

Suppose you are given a 3-ball $B$ in $\mathbb{R}^3$ that is bounded by a PL sphere, a triangulation $T$ of $B$ by Euclidean tetrahedra. Is that triangulation necessarily shellable? I know that if $...
Dylan Thurston's user avatar
5 votes
1 answer
257 views

Do random triangulation edge-flips maintain randomness?

Let $S$ be a fixed set of $n$ points in the plane in general position. Let $T$ be a triangulation of $S$, (somehow) selected uniformly at random from all triangulations of $S$. (There are an ...
Joseph O'Rourke's user avatar
5 votes
1 answer
213 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 "...
aglearner's user avatar
  • 14k
5 votes
1 answer
104 views

Sufficient condition for a Hamilton cycle $C$ in a planar triangulation $G$ s.t. every triangle in $G$ has an edge in $C$

Let $G$ be a $k$-connected planar triangulation ($k\geq 4$) and let $C$ be a Hamilton cycle of $G$. Then: Which conditions would be sufficient to assure that every triangle of $G$ has at least one ...
Jose Antonio Martin H's user avatar
5 votes
0 answers
202 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 ...
Dmytro Taranovsky's user avatar
5 votes
0 answers
221 views

Are there non-cuspy triangulations of smooth manifolds?

In (as it turned out my misunderstanding of) the literature, a "smooth triangulation" seems to mean: a homeomorphism from a simplicial complex, such that on each simplex the map can be extended to a ...
Vivek Shende's user avatar
  • 8,663
5 votes
0 answers
237 views

(∞,n)-category of triangulated cobordisms

What is an accepted definition of a (∞,n)-category of triangulated cobordisms? Is there one that has a forgetful functor to (Rezk - Hopkins -) Lurie's smooth cobordisms? Does it shed light on how ...
Manuel Bärenz's user avatar
4 votes
1 answer
362 views

Triangulation of a simplex

I am looking for a triangulation of an $n$-dimensional simplex such that all sub-simplices are of comparable size, and are "as close as possible" to a regular simplex : the latter property ...
Bruno's user avatar
  • 43
4 votes
1 answer
283 views

Do combinatorially equivalent polytopes have the same triangulations?

A triangulation of a convex polytope $P\subset\Bbb R^n$ is a partition of $P$ into $n$-simplices $\{\Delta_1,...,\Delta_m\}$ each of which has all its vertices among the vertices of $P$. A polytope ...
M. Winter's user avatar
  • 12.5k
4 votes
2 answers
340 views

Complexity of Random Delaunay Triangulation in 3D

My question: Is the number of cells in a three-dimensional Poisson-Delaunay triangulation with $n$ vertices $\mathcal O(n)$ with probability one? which is equivalent to the question Is the ...
Dahn's user avatar
  • 141
4 votes
1 answer
318 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 ...
domotorp's user avatar
  • 18.3k
4 votes
1 answer
161 views

Ideal triangulation of hyperbolic 3-manifold with generic mapping class group

I am from physics background so I apologize in advance if my question is trivial. Kojima proves for every finite group $G$, there is a hyperbolic 3-manifold such that its mapping class group equals $G$...
Zhengdi Sun's user avatar
4 votes
1 answer
2k views

On Thurston's triangulations of sphere

I have two questions from Thurston's paper [1]. In the paper [1], Thurston talks about classifying certain classes of triangulations of the sphere. Here a triangulation of a sphere a Topological ...
hrkrshnn's user avatar
  • 239
4 votes
1 answer
168 views

Geometric realization of an abstract triangulation of the plane

Can every abstract simplicial complex whose geometric realization is homeomorphic to $\mathbb{R}^2$ be realized by a rectilinear triangulation of the Euclidean plane? Alternatively put, can a curvy (...
Allan Edmonds's user avatar
4 votes
1 answer
169 views

The number of simplicial and general $d$-polytopes with $d+3$ labelled vertices

Micha Perles used Gale diagrams to compute the number of simplicial $d$-polytopes with $d+3$ vertices and of general $d$-polytopes with $d+3$ vertices. The computation can be found in Chapter 6.3 of ...
Gil Kalai's user avatar
  • 24.2k
4 votes
1 answer
938 views

Simplex in convex polytope, pulling triangulation

Let $P$ be a convex $d$-dimensional polytope. I have two questions, related to triangulations of $P$. Question 1: Let $p$ be in the interior of $P$. Can I always find a triangulation of $P$, such ...
Per Alexandersson's user avatar
4 votes
0 answers
118 views

Triangulating piecewise-linear manifolds

Question 1: Is this the mainstream definition of a PL-manifold? Definition. A PL-manifold is a manifold with an atlas $(\varphi_i)_{i\in I}$ in which all transition maps $\varphi_j\circ\varphi_i^{-1}$ ...
Vadim's user avatar
  • 346
4 votes
0 answers
100 views

Retriangulating manifolds via triangulations of low local complexity

Suppose that $M$ is closed, connected PL $n$-manifold. We say that a triangulation of $M$ has local complexity at most $L$ if every zero-cell of $T$ meets at most $L$ $n$-simplices. (An alternative ...
Sam Nead's user avatar
  • 26k
4 votes
0 answers
159 views

(Non-)Orientability of non-triangulable manifolds

We heard and learned from Mike Miller's answer to Not all manifolds can be triangulated: In which dimensions? that "All orientable 5-dimensional manifolds are triangulable. In dimensions at least ...
annie marie cœur's user avatar
4 votes
0 answers
280 views

Mean number of $n$-simplices per $(n-2)$-simplex in a triangulated $n$-manifold

Work by Tamura (extending results by Luo and Stong) shows the following. Theorem: For any closed 3-manifold $M$ and any rational number $4.5 < r < 6$ there is a triangulation $T$ of $M$ for ...
Aaron Trout's user avatar
3 votes
2 answers
307 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 ...
Joseph O'Rourke's user avatar
3 votes
1 answer
198 views

Is every (not necessarily PL-) triangulation of a manifold pure, non-branching and strongly-connected?

A triangulation of a topological manifold $\mathcal{M}$ possibly with boundary is an abstract simplicial complex $\Delta$ together with a homeomorphism $\varphi:\vert\Delta\vert\to\mathcal{M}$, where $...
B.Hueber's user avatar
  • 987
3 votes
1 answer
2k views

practical algorithm for constrained triangulation in two dimensions?

I'm looking for an algorithm that is easy to implement in practice (resulting in small amount of code), preferably incremental. As far as I know, the biggest problem with incremental constrained ...
nem's user avatar
  • 131
3 votes
1 answer
437 views

Dehn-Sommerville relations for $\Delta$-complexes

Let $M$ be a closed, triangulated manifold of dimension $m$ and $K(M)$ be its triangulation. Let $f_i$ denote the number of $i$-simplices of $K(M)$. As proved by Klee the face numbers satisfy the ...
Priyavrat Deshpande's user avatar
3 votes
1 answer
211 views

Handle attachment information from Morse function and triangulation

First, allow me to setup the relevant information. It is well known that a Morse function $f:M\to\mathbb{R}$ induces a handle decomposition of $M$. For simplicity, let's restrict for now to the ...
rab's user avatar
  • 139
3 votes
1 answer
118 views

Uniqueness constraints for Delaunay triangulation

Commonly the assumption that is made on point sets that shall be Delaunay-triangulated is that no three are collinear and no four are cocircular. Those assumptions are however too restrictive: if ...
Manfred Weis's user avatar
  • 12.6k
3 votes
1 answer
118 views

Surfaces generated by minimum-weight triangulations

The minimum-weight triangulation of simple polygons can be efficiently calculated in $O(n^3)$ time by dynamic programming, while it is $\text{NP-hard}$ for pointsets in general. Looking at the ...
Manfred Weis's user avatar
  • 12.6k
3 votes
0 answers
49 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 ...
Maaz's user avatar
  • 131
3 votes
0 answers
90 views

Minimal set of geometric moves in various equivalence classes of triangulated geometries

I would like to get to know what is the minimal set of geometric changes "aka. moves" (topology preserving modifications / Pachner moves / bistellar moves) that can transform any 3-...
Kregnach's user avatar
3 votes
0 answers
210 views

Category of Manifolds and Maps: TOP $\supseteq$ TRI $\supseteq$ PL $\supseteq$ DIFF? [closed]

Please let me denote the following (TOP) topological manifolds https://en.wikipedia.org/wiki/Topological_manifold (PDIFF), for piecewise differentiable https://en.wikipedia.org/wiki/PDIFF (PL) ...
annie marie cœur's user avatar
3 votes
0 answers
99 views

Find a certain triangulation subordinate to a given covering of a manifold

Let $\{U_\alpha\}$ be a covering of a smooth manifold $M$. Replacing it by a refined covering if necessary, we may assume some good properties of it, like, (1) any intersection $\cap_{i=1}^k U_{\...
Hang's user avatar
  • 2,719
3 votes
0 answers
368 views

regular triangulations of the product of two simplices

Is description of all regular triangluations of $\Delta^n\times \Delta^k$ known? (Regular triangulations are those which correspond to vertices of Gelfand--Kapranov--Zelevinsky secondary polytope, or, ...
Fedor Petrov's user avatar
2 votes
2 answers
698 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 ...
shurtados's user avatar
  • 1,010
2 votes
1 answer
179 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 ...
Selim G's user avatar
  • 2,626
2 votes
1 answer
73 views

Calculating a relaxed Delaunay Triangulation

The triangles of a planar Delaunay Triangulations are essentially characterized by the property that no triangle's corner is inside another triangle's circumcircle; Delaunay Triangulations can be ...
Manfred Weis's user avatar
  • 12.6k
2 votes
1 answer
128 views

Two ears polygon in a maximal planar hamiltonian graph

Given a maximal planar graph (+6vertices) without separating triangles. Then it can have many Hamilton cycles°. Such a cycle divides the graph into two triangulated polygons. Is it always possible to ...
P.Labarque's user avatar
2 votes
1 answer
114 views

mean length of the non-crossing graphs on n points

My original question is rather vague so I'll start with a precise example and then indicate possible generalisations. Given a n-tuple $x=(x_1,\dots,x_n)$ in, say, a square with side-length $1$ in the ...
kaleidoscop's user avatar
  • 1,268
2 votes
0 answers
67 views

Triangulations with discrete metrics and conformal equivalence

A discrete metric for a triangulation of a 2-dimensional manifold is a map associating $\mathbb{R}_+$-valued lengths to all edges, such that the triangle inequality holds on every triangle. In many ...
Andi Bauer's user avatar
  • 2,901
2 votes
0 answers
60 views

Relation between symmetries of hyperbolic knot and the symmetries of a generic triangulation

For canonical ideal triangulation of a hyperbolic knot, the symmetries of the knot are the same as the symmetries of that triangulation. This is how SnapPy computes the knot symmetry group. Is there ...
Zhengdi Sun's user avatar
2 votes
0 answers
23 views

What is known about $\operatorname{card}_E(\mathrm{MST}\cap\mathrm{MWT})$?

It is a wellknown fact of computational geometry that the edges of Minimum-weight Spanning Tree are also found in the Delaunay Triangulation of a planar pointset $\mathcal{P}$, i.e. $\operatorname{...
Manfred Weis's user avatar
  • 12.6k
2 votes
0 answers
50 views

Triangulations of conformal manifolds

I'm seeking for a discrete representation of $2$-manifolds with a conformal structure (i.e. metric modulo scalar prefactor). The topology of a $2$-manifold is determined by the combinatorics of a ...
Andi Bauer's user avatar
  • 2,901
2 votes
0 answers
86 views

Existence of a "generic enough" lattice point interior to a lattice triangle

Let $T$ be a lattice triangle in $\Bbb R^2$ (i.e. the convex hull of three noncolinear points in $\Bbb Z^2$), and assume it has at least one interior lattice point. Is it always possible to find a ...
Avi Steiner's user avatar
  • 3,031
2 votes
0 answers
122 views

Does any smooth oriented closed orbifold have a fundamental class

This thread:triangulation of orbifolds has shown that any smooth closed orbifold has a triangulation. My further question is: if the difference of any two triangulations $P$ and $Q$ is a boundary of a ...
Hao Yu's user avatar
  • 771
2 votes
0 answers
98 views

Existence of triangulation of Lipschitz domains

Consider a bounded Lipschitz domain $\Omega \subset \mathbb R^n$. Q1: Can its closure $\overline\Omega$ be triangulated? Q2: If yes, can the triangulation be chosen as finite? Furthermore, how ...
shuhalo's user avatar
  • 4,736
2 votes
0 answers
164 views

Homotoping a 2-plane field on a closed orientable 3-manifold to a contact structure

I am a beginner in Contact Geometry. To prove that the inclusion $\text{Cont}(M)\hookrightarrow \text{Dist}(M)$ induces surjection at $\pi_0$ level, the closest I got was based on Ko Honda's notes. ...
Karthik C's user avatar
  • 261
1 vote
1 answer
83 views

Is every triangulation the projection of a convex hull

Question: given the triangulation $T$ of a set $P$ of $n$ points $p_1,\dots,p_n$ in the euclidean plane whose convex hull is a triangle, can we always find a set $Q$ of $n+1$ points $q_0,q_1,\dots,q_n$...
Manfred Weis's user avatar
  • 12.6k
1 vote
1 answer
69 views

Partitioning polygons into obtuse isosceles triangles

Ref: Partitioning polygons into acute isosceles triangles Partition of polygons into 'strongly acute' and 'strongly obtuse' triangles https://math.stackexchange.com/questions/1052063/...
Nandakumar R's user avatar
  • 5,473