Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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

0
votes
0answers
19 views

intersection in a simplex

In a triangulation $\Gamma$ of a (oriented) 2-manifold, consider a 2-simplex labeled by ($123$), where $1,2,3$ denote the order of vertices. Consider the dual $\Gamma^*$ of $\Gamma$, and then denote ...
0
votes
0answers
40 views

Delaunay triangulation in $\mathbb R^d$: Empty sphere property works for all $k$-faces?

This is (it seems to me) a well-known fact, but I am struggling to find a reference. Let $X=\{x_1,\dots, x_n\}\subset \mathbb R^d$ be a set of points. Then the following is true: Subset $F\subset ...
0
votes
1answer
87 views

Triangulation (position location) on a plane

I'm trying to solve a problem that to me is "triangulation" but searching to see if it's been answered before makes me think that this word has a different meaning to pure mathematicians. Broadly, I'...
0
votes
1answer
20 views

Simple triangulation over flat torus

This is somewhat of a computational question: let me know if it is inappropriate. I have a flat torus with sone random points marked. I would like to compute a triangulation of said torus such that ...
1
vote
0answers
22 views

Clarification on How to derive Voronoi diagram from Delaunay triangulation in linear time

Definitions: Assume that a set of points $P=\{p_1,\dots,p_n\}$ in $\mathbb R^d $ is given. For each $p_i \in P$, the Voronoi region of $p_i$ is defined as: $Vor(p_i)=\{p\in\mathbb R^d:\forall p_j\in ...
0
votes
0answers
7 views

Triangulation of a n.simplex

What is the definition of a triangulation of an n-simplex. My intuition tells me that we divide the simplex into smaller simplexes but I do not know what other things should be fulfilled
0
votes
0answers
24 views

Coloring triangles in a Delaunay triangulation on the surface of a 3d sphere.

Suppose a delaunay triangulation over the surface of a 3d sphere (or generally some 3d surface of something topologically equivalent to the sphere). How many colors do I need to color its triangles so ...
0
votes
0answers
28 views

Estimate coordinates of vertices

Let $\hat{t}$ be the reference triangle with the vertices $\hat{A_1} = (0,0)$, $\hat{A_2} = (1,0)$, $\hat{A_3} = (0,1)$ and let $t$ be the triangle with the vertices $A_1 = (0,0)$, $A_2 = (h_1, 0)$ ...
1
vote
1answer
25 views

How can I create an evenly distributed mesh from a shape?

I'm trying to convert some 2D shapes (without holes) into meshes with evenly distributed vertices. Before the conversion the shapes are edge loops with no internal vertices. After the conversion I ...
0
votes
0answers
15 views

Estimation of relation between vertices of a triangle

Let $\hat{t}$ be the reference triangle with the vertices $\hat{A_1} = (0,0)$, $\hat{A_2} = (1,0)$, $\hat{A_3} = (0,1)$ and let $t$ be the triangle with the vertices $A_1 = (0,0)$, $A_2 = (h_1, 0)$ ...
0
votes
0answers
32 views

Is there an easy way to find the sign of this determinant without calculating it directly?

There exist real numbers $A_x, A_y, B_x, B_y, C_x, C_y, D_x$ and $D_y$. Is there an easy way to find the sign of following determinant without calculating it directly? BTW, the determinant appears ...
0
votes
1answer
45 views

Trilateration when only combinations of distance are available

My problem setup is as shown below: I know the location (x,y) of fixed points p1+, p1-, <...
1
vote
2answers
39 views

Calculate C point of triangle given A, B, angle a, angle b

One pic is worth thousand words... I know angle a, angle b, pointA, ...
0
votes
1answer
18 views

Biholomorphic functions and delaunay triangulation

Lets have a look at the two simply connected domains $D,G \subset \mathbb{C}$ and a biholomorphic function $f:D \rightarrow G$ which maps $D$ conformal onto $G$. For some $n \in \mathbb{N}$ there ...
0
votes
1answer
53 views

Numerical integration in Finite Element Method (and implementation in Matlab)?

i'm trying to solve the p-Laplace Equation: \begin{align} \begin{cases} \text{div} (\sigma |\nabla u|^{p-2} \nabla u) = f &\quad \text{in } \Omega\\ u = g &\quad \text{in } \partial\Omega \...
0
votes
1answer
9 views

Lower bound on the number of faces incident to a set of vertices in a planar triangulation

Suppose that $G$ is a planar triangulation (also the outer face has to be triangle) on $n \geq 4$ vertices. Let X be a subset of vertices of $G$ such that $|X| \leq n-3$. Let $F(X)$ be the set of all ...
1
vote
0answers
27 views

Blindly removing inessential diagonals from a triangulation can lead to a bad convex partitioning

Assume that a simple polygon $P$ and a triangulation of it only using the diagonals is given. We say a diagonal $d$ is essential for vertex $v$ if removing $d$ creates a piece that is nonconvex at $v$....
1
vote
1answer
34 views

Is this a triangulation for the 2-torus?

I am not quite sure I understand simplicial comlexes/triangulations. For instance, I think that the below image represents a triangulation for the 2-torus. Am I correct?
0
votes
0answers
149 views

Induction Problem with Polygon Triangulation rules

Problem: Let P be a convex polygon with consecutive vertices v1,v2,...,vn. Use some form of induction to show that when P is triangulated into n−2 triangles, the n−2 triangles can be numbered 1,2,...,...
0
votes
1answer
49 views

triangulation of a circle and the way to solve a problem

Consider the circle $S^1$ with multiplication given by the complex numbers. Prove that the map $f(x) = x ^n$ , $n$ a positive integer, has degree $n$. What is the degree of the map $g(x) = 1/x$. ...
0
votes
0answers
26 views

Why does skinny triangle is avoided in triangulation algorithm?

I recently learned about Delaunay triangulation algorithm.. One property of this algorithm is to prevent the generation of skinny triangles.. However, I haven't really seen any good explanation of why ...
3
votes
1answer
86 views

Use of the integrals in the graph theory

I hope to know some good references about the use of integrals to study the graph theory: For example, it seems that $$ \int^{\infty}_{-\infty} dx \exp(-x^2/2+\lambda x^3/3!) $$ whose coefficients in ...
9
votes
2answers
493 views

Catalan numbers and triangulations

The number of ways to parenthesize an $n$ fold product is a Catalan number in the list $1,1,2,5,14,\cdots$ where these are in order of the number of terms in the product. The $n$th such number is also ...
1
vote
0answers
43 views

Simultaneous movement toward barycenters - what can be guaranteed

Suppose a tiling is given in 2D (an embedding of a planar triangulated graph), with all faces convex. Now suppose one moves each point, one by one, to the barycenter of its neighbors. I think that ...
0
votes
0answers
28 views

Why does “angle defect” work as a global measure of flatness or lack thereof?

In "Non-Euclidean Geometry and Curvature" by James W. Cannon, the author states that the "angle defect" def(D) of a polyhedral disk D works "as a global measure of the degree to which D fails to be ...
1
vote
1answer
58 views

Number of triangles in any triangulation of a 2-d figure

We are given a figure like this in the plane. Does any triangulation without addition of new vertices of such a figure have the same number of triangles? For a polygon, I know any triangulation gives ...
5
votes
2answers
114 views

Probability that a delaunay triangle contains the center of its circumcircle

A Delaunay triangulation for a given set P of discrete points in a plane is a triangulation DT(P) such that no point in P is inside the circumcircle of any triangle in DT(P). https://en.wikipedia.org/...
0
votes
0answers
29 views

Euler Characteristic of figure(piecewise linear complex - 2d)

I want to calculate the Euler characteristic of this $2$-dimensional piecewise linear complex. A piecewise linear complex is a finite set of linear cells - vertices, edges and polygons( not ...
0
votes
0answers
15 views

What separates a cyclic polytope from a projective polytope?

I am having trouble understanding the difference between a cyclic polytope and a convex projective polytope as positive geometries. The link https://arxiv.org/pdf/1703.04541.pdf is the source of ...
0
votes
1answer
48 views

Triangulation and Linear Systems

I'd like to ask your help to solve a linear system related to a triangulation problem involving two rays (vectors). Let $a\textbf{p}_{l}$ ($a \in \mathbb{R}$) be the ray $l$ through $O_{l}$ ($a = 0$) ...
2
votes
1answer
74 views

Find a point related to triangle.

I have two triangles that are not similar. The Only thing that I know is that AB and C points from triangle 1 are related to $A^1 B^1$ and $C^1$ points from triangle 2. Based on these inputs I want ...
1
vote
0answers
42 views

Interpolation via triangulation between a set of points on two parallel lines

I'm trying to develop a fast algorithm to perform 2D interpolation between two parallel lines. Along the way, I found an interesting problem and have been wrestling with it for longer than I should. ...
3
votes
1answer
80 views

Can't find an equation for calculating when 4 moving points have a circle passing through them

First thing - please forgive me if my way of explaining my problem is not formal or not accurate to standards, I am an amature mathematician and I have much to learn, I welcome you to let me know ...
0
votes
1answer
44 views

Determine relative coordinates of a point inside a triangle with only distances known

Say I have a triangle with points A, B, and C, and I know the lengths of AC, AB, and BC. The triangle may or may not be a right triangle. Example: click here, I can't embed the image since I don't ...
0
votes
1answer
55 views

Is there something wrong with my simplified in-circle predicate?

My larger goal is to write a program that performs 2D constrained Delaunay triangulations. My smaller, current goal right now is to write a predicate function that determines if an edge is locally ...
0
votes
0answers
9 views

Is $D \cap \mathbb{Z}^d = \mathbb{Z}_+^d$ where $D$ is a unimodular cone?

Let us consider a polytope $P$ in $\mathbb{R}^d$ such that it lies in positive quandrant of each componennt i.e. $\mathbb{R}_+^d$. Assume $P$ has a unimodular trangulation $\Sigma$ such that each $D \...
3
votes
1answer
42 views

Are triangulations of polygons 3-colourable?

Let us take a polygon and divide it into triangles in an arbitrary manner. When playing with such triangulations, I was not able to generate any which were not 3-colourable. Is it true in general ...
0
votes
0answers
9 views

Is it possible to increase the size of enclosing triangle in the Bowyer-Watson algorithm after the algorithm has done some work

Lets say i have a set of points A. I want to triangulate these points. Using Bowyer-Watson on A i get the corresponding triangulation T. No i want to introduce a set of new points S to A. All the ...
0
votes
0answers
95 views

Delaunay Triangulation in 3D

I am planning to construct a CAD model from a point cloud. The point cloud is a list of unique 3D point. The CAD model is a list of triangles (2D triangles not tetrahedra) in a 3D space. Lets say ...
0
votes
1answer
49 views

Cutting a square into non-similar triangles [closed]

Is it possible to cut a square into an infinite number of triangles, so that all of them are non-similar?
0
votes
0answers
44 views

Lay out a set of random circles without intersections

I am trying to write an algorithm that will take a set of circles C where some of the circles may intersect or overlap. Their centers and radii are random. The output of this algorithm should be a set ...
1
vote
2answers
55 views

Finding the location of point P

Is it possible to find the location of point $P$ such that the angles $\theta_1=\theta_2$ or $\alpha_1=\alpha_2$? I know only the locations of $O$, $C_1$, and $C_2$.
0
votes
1answer
49 views

Prove that no set of $n$ points can be triangulated in more than $2^{n \choose 2}$ ways.

Prove that no set of $n$ points can be triangulated in more than $2^{n \choose 2}$ ways. So I am really confused about the argument. We have two choices to triangulate 4 sided polygon. So the ...
1
vote
0answers
88 views

Is this a valid triangulation of Moebius strip?

This is a quick sanity check. I'd like to know if the diagram I've created is a valid triangulation of the Moebius strip or not.
1
vote
0answers
28 views

Fake torus triangulation in Munkres [duplicate]

It's mentioned in Elements of algebraic topology (Munkres) that the following figure is not a valid triangulation of torus because it "does more than paste opposite edges together". Q: What's ...
1
vote
1answer
111 views

Triangulation of the projective plane (number of points required)

I am trying to understand the triangulation of a projective plane and it has been proven that minimally we need six points to triangulate. But I do not understand why a rectangle above (using 3 ...
-3
votes
1answer
80 views

find a distance between 2 points on x-axis

Problem Graph A person walked a distance of 10m from (0,0) to (10,0) - final distnation; prior to reaching final distancetion he stopped betwen 2 points (a,0) and (b,0). The distance between (a,0) ...
0
votes
1answer
38 views

Need help in understanding the argument in a proof of polygon triangulation

I cannot really understand the highlighted argument. I have feeling that the statement is correct, but I do not understand the argument that proves it. Thank you!
1
vote
0answers
69 views

Is there a shortcut to the construction of the concave hull of a set of 2D points (alpha shape)

In 2D, concave hulls of a set of points (also called alpha shapes) can be obtained by discarding from the Delaunay triangulation of the points those triangle with a circumscribed radius exceeding ...
3
votes
1answer
46 views

Is the following triangulation valid?

Consider the following polygon with 10 vertices such that $H,G,F,I$ are colinear: Note that it is known that any triangulation of a polygon with $n$ vertices gives has $n-2$ triangles. In the figure ...