Stack Exchange Network

Stack Exchange network consists of 175 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
1answer
12 views

Systematic approach to triangulation closed combinatorial surfaces

I was wondering whether there is a systematic approach to the triangulation of closed combinatorial surfaces, which we know can be shown to be homeomorphic to polygons with complete set of side ...
1
vote
0answers
28 views

Triangulation with 3 known points and time is involved?

I am completely stuck on how to visualize this problem, let alone code it. Understanding the mathematics behind it could help me out a lot. Thanks! Let's suppose that the unknown point is actually a ...
1
vote
1answer
23 views

Riemann Mapping theorem in triangulations

I am reading the paper 'Rotation Distance, Triangulations, and Hyperbolic Geometry' by Thurston et al. The authors are constructing a sequence of triangulation from a regular icosahedron. Each face of ...
1
vote
1answer
20 views

Inverse of Simplicial Isomorphism also Simplicial Isomorphism?

Is it true that inverse of a Simplicial Isomorphism is also a Simplicial Isomorphism? Let $\phi$ be a simplicial map and a homeomorphism from $|K_1|$ to $|K_2|$, for any $g \in K_2$, $\phi^{-1} \circ ...
1
vote
1answer
69 views

Calculate the circle that touches three other circles

Given three circles on a cartesian grid (with centres and radii known), how would you calculate the centre of the circle that touches those three? The three known circles may have any radius length, ...
0
votes
0answers
55 views

Topological space formed by the identification of a unit square

I know that the first identification "rolls up" the unit square to form a cylinder with open ends but I'm unsure on how the next two "close up" the ends. Does it become a cylinder or more of a cone ...
0
votes
0answers
35 views

Getting plane equation having side's length and an angle of triangle

How can I get plane equation or normal vector of "a" side? I have problem with it and didn't find solution. I wonder if I can get plane equation having only parameters shown on a picture or I ...
0
votes
1answer
37 views

“Reverse Direction” of the Euler Characteristic for a Triangulated Space

If $X$ is triangulated, the Euler characteristic of the triangulation is the alternating sum $f_0 − f_1 + f_2-...$ where the number $f_n$ counts the n-simplices in the triangulation. I know that any ...
0
votes
0answers
26 views

Property of a quasi-uniform triangulation

I have some type of proof for the inverse inequality: $|\nabla v |_{H^1} \le C |v|_{H^1}$ This proof uses the following property for quasi-uniform triangulations: $ \frac{\int_{{K}^\wedge}{|\nabla v^\...
0
votes
0answers
23 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
43 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
101 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
22 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
26 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
27 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
29 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
16 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
75 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
44 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
19 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
71 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
29 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
57 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
152 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
108 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
27 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
87 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
582 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
29 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
70 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
126 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
33 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
53 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
76 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
55 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
50 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
66 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
11 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
52 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
105 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
54 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
57 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$.