# Tag Info

## Hot answers tagged triangulation

Accepted

### Efficiently finding point triangle inclusion when doing incremental delaunay triangulation?

These parts of the algorithm are discussed in the book Computational Geometry by de Berg et al. I will provide a summary here. Let $P$ be the set of input points. Make 3 points that are large enough ...
• 8,303

### Convex Polygon Triangulation: Line Intersects at most $O(\log n)$ Triangles

Let the polygon be defined by the vertices in clockwise order: $(v_1, \dotsc, v_n)$. For simplicity, assume that $n$ is even. Add the lines: $(v_1,v_3)$, $(v_3,v_5)$,...,$(v_{n-2},v_1)$. Then, ...
• 6,187

### Fast measurement of distance from point to mid segment?

If you use an under-/overflow-safe euclidean norm implementation along the lines of LAPACK's dnrm2, your line-to-point distance function will look something like the following Scala code: ...
• 991
1 vote
Accepted

### How to avoid global delaunay check in conforming triangulation?

I figured it out. The implementation of lawson's algorithm I had was incorrect, this is the right one: ...
• 341
1 vote

### Constrained Delaunay triangulation algorithm?

Page 7 of "FAST ALGORITHM FOR GENERATING CONSTRAINED DELAUNAY TRIANGULATIONS" (a publication on a CDT algorithm) explains the process very clearly and the figures are extremely useful.
• 341
1 vote
Accepted

### Constrained Delaunay triangulation algorithm?

You can find Johnathan Shewchuck's UC Berkely website here, which contains: Excellent lecture notes on Delaunay Mesh Generation sample chapters from the book "Delaunay Mesh Generation" (...
• 991
1 vote

### Inflate a polyline so that the 2D band can be triangulated without self-intersections

I think your "inflated polyline" can be correctly defined as a union of "inflated line segments". Each such "inflated line segment" will be a rectangle with half-disks on ...
• 3,098
1 vote

### Convex polygon triangulation with stabbing number O(log n)

In the recursive triangulation you consider, you roughly divide the number of vertices by $2$ at each level of recursion. Thus, there are $O(\log n)$ levels of recursion. Consider some segment $S$. ...
• 2,522
1 vote
Accepted

### Delaunay triangulation from an EMST

The Wikipedia article states, that: the Delaunay triangulation can be constructed from the Euclidean minimum spanning tree in the near-linear time bound $O(n\log ^{*}n)$, where $\log ^{*}$ denotes ...
• 3,098

Only top scored, non community-wiki answers of a minimum length are eligible