Questions tagged [triangulation]
For questons about triangulation, that is a) the subdivision of the plane or other topological spaces into triangles (or, more generally, simplices) or b) the methods used in surveying for locating points by measuring angles and accessible lengths of triangles
448
questions
1
vote
1
answer
50
views
Triangulation trigonometry
I’ve been looking at triangulation calculations, and I’ve become a bit stumped as to how the authors of the attached document have come to the following calculations.
In the page it explains how one ...
- 11
5
votes
1
answer
525
views
Can one compute the location of the unseen point?
My question is quite simple. I have two images, on the first one I know the location of points $P1, P2, P3$, and $P4$. In the second image, I know the location of $P2'$, $P3'$, $P4'$, and point $Q'$. ...
- 61
0
votes
0
answers
56
views
Ordered Delaunay triangulations
I would like to show that, given n points in the plane $q_1 ... q_n$ such that the distance between $q_0$ and $q_i$ is smaller than or equal to the distance between $q_0$ and $q_j$ for every $i < j$...
- 81
0
votes
1
answer
37
views
Do two triangulations of a smooth manifold have a common subdivision?
The Hauptvermutung (ie. the question in the title) is known to be false for PL manifolds and topological manifolds, but I can't find a result for smooth manifolds (with boundary), though I recall ...
- 6,303
1
vote
0
answers
49
views
Why are there only finitely many simplicial maps from one polyhedron to another?
I don't understand why for two polyhedra $|X|$ and $|Y|$, there are finitely many choices of simplicial maps $$s: |X^m| \rightarrow |Y|$$ for some large enough $m \in \mathbb{N}$. Multiple sources say ...
1
vote
1
answer
57
views
Bicolored triangulations of $S^2$ with certain conditions on degrees of vertices
Finite sets $B,W\subset\mathbb N^2$ are given. Suppose $G=(V,E)$ is a triangulation of a two-dimensional sphere so that $V=V_b\sqcup V_w$. We say that $G$ is a $(B,W)$-triangulation if $(\deg_bv,\...
- 235
2
votes
1
answer
155
views
Triangulation vs. Trilateration
Are triangulation and trilateration different words for the exact same procedure, or is there a small technical difference between the two?
If there is a small difference, which is the correct term ...
- 163
1
vote
0
answers
35
views
Does every smooth manifold have a Hamiltonian triangulation?
Call a triangulation of a smooth manifold Hamiltonian if its 1-skeleton has a Hamiltonian cycle. I have several questions about these that I haven't been able to find answers to. First, every smooth ...
- 6,303
0
votes
0
answers
32
views
Are these maps homotopic relative to a finite set of points?
Let $M,N$ be (compact) smooth manifolds and consider a triangulation $\mathcal{T}$ of $M.$ Consider two maps $f,g:M\to N$ which agree on the vertices of the triangulation. Is it true that $f$ and $g$ ...
- 6,303
1
vote
1
answer
53
views
Why does direct linear transform (DLT) yield a unique solution?
I try to triangulate point correspondences from 2 images in order to reconstruct the 3D positions of those points.
I found the DLT method as an easy way to achieve that. The system which needs to be ...
- 151
5
votes
0
answers
190
views
Counting problem about polygon triangulations
I have the following question about triangulations (by non-intersecting diagonals, and edges) of regular polygons.
What is the number of triangulations of a regular n-gon, up to all symmetry (i.e. the ...
- 632
0
votes
0
answers
67
views
3-dimensional triangulations with fixed number of vertices
My question is the following:
Are there triangulations of $S^3$ which (a) are non-degenerate, (b)
have four vertices, and (c) have no edges of degree two?
Here are the definitions.
We use labeled ...
- 43
0
votes
1
answer
32
views
Package to enumerate all regular triangulations for point configuration
I am trying to enumerate the regular triangulation of some point configurations. The sage-math can enumerate all triangulations, but cannot check if each one is regular or not.
It seems TOPCOM can ...
- 139
4
votes
1
answer
188
views
Does every surface admit a quadrangulation?
Every surface (2-manifold) admits a triangulation, and I wonder if the same can be said for quadrangulation.
My intuition is that every orientable surface can be quadrangulated, but I'm not sure about ...
- 6,137
0
votes
0
answers
10
views
Local h-polynomial with V=3.
I'm trying to understand an example that Stanley gives in his article "Subdivisions and local h vectors". It is example 2.3 part d).
If #V=3 and $h(\Gamma,x)=h_0+h_1x+h_2x^2+h_3x^3$ (so $...
- 1
0
votes
1
answer
74
views
Why isn't this a correct triangulation of the torus/projective plane?
This is to be proven an incorrect triangulation of the torus:
And this is to be proven an incorrect triangulation of the projective plane:
I would like to know what part of the definition of ...
2
votes
1
answer
85
views
Triangulation of a surface
In their 2015 paper on random simplicial complexes, Costa and Farber
casually mention without a proof that in triangulation of a closed surface, there is a formula
$$\frac{\text{number of $1$-faces}}{\...
- 403
0
votes
0
answers
38
views
Triangulations of square grids
If you have a square two-dimensional grid, that are lots of ways it could be triangulated -- for an individual square one could add an edge from upper-right to lower-left, or from lower-right to upper-...
- 279
1
vote
1
answer
81
views
Non-delaunay triangulation of a set of points and its convex hull boundary
I have a set of n random points on a 2D plane, and its convex hull boundary. Some points lie interior to the convex hull boundary. I want to triangulate this in a non-delaunay random fashion, such ...
- 63
0
votes
0
answers
51
views
Rotating matrices to display data from radar onto a HUD
I'm trying to write a code (in-game scripts) that takes data from radar (distance, azimuth, elevation) and displays points on a HUD in front of the player. Yesterday, I've managed to visualize radar ...
- 1
0
votes
1
answer
36
views
Second closest red-blue theorem
I want to prove/disprove that for a set $S = R \cup B$ of $n \geq 3$ colored (red and blue) points in general position (no 3 are collinear, no 4 are cocircular, and the distances between the $n \...
- 63
0
votes
0
answers
23
views
Unique intersections of n-dimensional hyperspheres/Trilateration in n dimensions
Is it the case that when trying to locate an object in $n$ dimensions based on distances to known points, in general distances to $n+1$ unique points are required?
I think a way to tackle this is to ...
- 1
3
votes
0
answers
50
views
Identifying the delaunay simplex the point resides in without computing all the possible simplices
My question is whether it is possible to identify the delaunay simplex the point $\mathbf{x}_{\textrm{query}}$ resides in without pre-calculating all the possible simplices by triangulation?
Can we ...
- 31
1
vote
0
answers
50
views
Show that length of longest edge in Delaunay triangulation goes to zero
Suppose that we have a set of vertices $V$ in a certain space $\Omega$ and that we iteratively add a vertex to $V$ and build a Delaunay triangulation on these vertices. Now, if $\mathcal{T}^1$, $\...
- 83
2
votes
1
answer
116
views
Lifting triangulation by branched covering map
Let $X, Y$ be compact connected manifolds of the same dimension, and let $f : X \to Y$ be a branched covering with finitely many branch points. (For example, $f$ could be a holomorphic function ...
- 2,254
4
votes
1
answer
65
views
A single-color path in a two-color triangulated square
Take any triangulation of a square (= a partition into triangles such that any two triangles are either disjoint or intersect in a common face).
Suppose that there are no triangulation vertices on the ...
- 10.2k
0
votes
0
answers
13
views
If two combinatorial polytopes have a subset of their cocircuits in common, will they have a triangulation in common?
In "Triangulations" by Loera, Rambau, and Santos, there is a Corollary (4.1.44) that states that two combinatorially equivalent (having the same oriented matroid) point configurations have ...
- 1
1
vote
0
answers
25
views
Triangulation of the complement VS Complement of the triangulation
Consider a triangulable space $X$ in the $n$-sphere $S^n$ whose complement $X^c=S^n\backslash X$ is also triangulable: there exists finite simplicial complexes $T_X$ and $T_{X^c}$ whose geometric ...
- 13
0
votes
0
answers
68
views
How do you find an unknown point via the known location of other points and the angle of the unknown point when facing the known points?
Based on this previous question, but slightly different:
Find a point using multilateration or triangulation
Suppose we have 3 points in a 3d coordinate system with the following locations.
A=(100,0,0)...
0
votes
0
answers
19
views
$4$-connected Eulerian triangulations $T$ such that $T-e$ is 3-degenerate for some edge $e$
Do there exist $4$-connected plane Eulerian triangulations $T$ such that there exists some edge $e\in E(T)$ such that the graph $T-e$ is 3-degenerate? I cannot find any examples of such graphs, but ...
1
vote
0
answers
24
views
Isolate downward-facing faces of a convex hull
long time fan / first time poster here!
My question: is there an efficient algorithm for isolating just the downward-facing faces of a 3D convex hull?
In two dimensions, if one draws a line from the ...
2
votes
0
answers
63
views
Theorem 5, Section 6.4 of Hoffman’s Linear Algebra
Let $V$ be a finite-dimensional vector space over the field $F$ and let $T$ be a linear operator on $V$. Then $T$ is triangulable if and only if the minimal polynomial for $T$ is a product of linear ...
- 3,736
2
votes
1
answer
94
views
Ratio of largest to smallest distance in a set of six points is $\ge \sqrt 3$?
Here is problem A1 of 25th Putnam 1964.
Let $A_1, A_2, A_3, A_4, A_5, A_6$ be distinct points in the plane. Let $D$ be the longest distance between any pair, and $d$ the shortest distance. Show that $...
- 4,594
0
votes
1
answer
93
views
Triangulation formula in planar graph
What is the formula relating number of vertices $v,$ number of sides $s$ in a simple planar graph obtained by triangulating a polygonal region into $n$ triangles? Tried to find a constant out of $v+s-...
- 39.7k
1
vote
0
answers
55
views
DIFF = PL = TOP for surfaces (earliest references)
I am looking for the original references that show that there is essentially a unique PL and smooth structure on a topological manifold of dimension 2.
Radó ("Ueber den Begriff der Riemannschen ...
- 1,458
1
vote
0
answers
125
views
How to optimize a 2D triangle mesh for number of triangles?
I am currently writing a program where I have a set of points within a 2D plane that I would like to convert to a triangle mesh in such a way, that the mesh has the least number of triangles possible.
...
- 183
0
votes
1
answer
52
views
Calculating the numerical Hessian from an elevated Delaunay triangulation
Suppose I have an elevated Delaunay triangulation such as below:
Suppose the vertices are embedded as $(x_i,y_i,z_i) \in \mathbb{R}^3$ where $i \in \{1, \cdots, m \}$.
Let us assume that $z(x,y)$ is ...
- 1,800
0
votes
0
answers
78
views
Triangulating R^n
I am interested in triangulating $\mathbb{R}^n$ using the standard triangulation of $[0, 1]^n$.
By a triangulation of a subset $X \subseteq \mathbb{R}^n$, I mean a set of $n$-simplices $S$ whose union ...
- 1,074
0
votes
1
answer
71
views
Convex $n$-gons that can be decomposed into $2n$ right triangles
I was trying to prove that every convex $n$-gon can be decomposed into $2n$ right triangles. Here a sketch of the flawed proof:
$(i)$ Every convex $n$-gon with consecutive vertices $V_1, V_2, \dots, ...
- 1,152
0
votes
1
answer
36
views
Special point inside a convex polygon
After finding this interesting question, I was wondering how could be proved the existence of some point $P$ inside any convex polygon $C=\{v_1,v_2,\dots,v_n\}$, where $v_k$ is the $k_{th}$ vertex and ...
- 1,152
2
votes
0
answers
152
views
Distance between two points using triangulation
Suppose we have two points $p_1$ and $p_2$ in a metric space with $\bf{unknown}$ dimensionality, with no way to directly compute the distance between them, e.g. no coordinates.
Say we can randomly ...
4
votes
0
answers
93
views
Does a sphere always admit a triangulation in which the link of a vertex is a sphere?
In this question, it is asked whether for any triangulation $C$ of a sphere $S^k$, and for any vertex $v$ of $C$, the link of $v$ is homeomorphic to a sphere $S^{k-1}$.
This answer shows a concrete ...
- 10.2k
2
votes
0
answers
84
views
Triangulations of open sets in $\Bbb{ R}^n$
Can every open set in $\mathbb{R}^n$ be subdivided into a simplicial complex?
Here, a simplicial complex $K$ must be a locally finite set of simplices in some $\mathbb{R}^m$ such that each face of a ...
- 429
2
votes
2
answers
137
views
How to solve the triangulation problem?
I have $3$ sensors. I've built the following system of equations that match the data from sensors. I need to find $x$, $y$, $R_a$, $R_b$, $R_c$, $\alpha$, $\beta$ and $\gamma$. Can you please help me, ...
1
vote
0
answers
86
views
Show that a MST is a subgraph of the Delauney Triangulation
I am working on the following exercise:
Let $V$ be a finite set of points in $\mathbb{R}^2$. Consider
$$P_v := \{x \in \mathbb{R}^2 : \lvert\lvert x-v \rvert\rvert = \min_{u \in V} \lvert\lvert x - u ...
- 3,992
0
votes
1
answer
158
views
Upper triangulation of a matrix versus diagonalization
I am trying to google this question, but could not find any hints. This is important to me because of I am dealing with 3-4D matrices.
It's true that an upper triangulation (Gauss elimination) of a ...
- 1,493
1
vote
0
answers
59
views
Trilateration solution for N points with $D_{NxN}$ distances
Problem:
Let there be $N $ points $P_i(x_i,y_i,z_i)$
and a $\mathbf M$ the $NxN$ matrix of distances $d_{ij}$ between each point.
Lastly, let's consider that the 3 of the N points $P_1$, $P_2$ and $...
- 11
4
votes
1
answer
269
views
Fast algorithm to embed a triangulation into plane
Let $G = (V, E)$ be a planar graph such that $|E| = 3|V| - 6$ (so $G$ must be a triangulation without Kuratowski subgraphs). Given the adjacent matrix $A$ of $G$, please design an algorithm to embed $...
- 858
1
vote
1
answer
57
views
Triangulations of the Hyperbolic Plane
I'm studying triangulations of the hyperbolic plane and have come across the following theorem:
If we are given a triangle $\Delta_0$ with angles $\pi$/l,$\pi$/m,$\pi$/n, where the
integers l, m, n ...
- 55
2
votes
0
answers
101
views
Triangulation of 3-sphere and Hopf Fibration
I am currently reading the paper A Minimal Triangulation of the Hopf Map and its Application. In the paper, the authors are trying to describe a triangulation of the 3-sphere into a (abstract) ...
- 1,178