Skip to main content
3 votes
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 ...
Discrete lizard's user avatar
  • 8,303
3 votes

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, ...
Inuyasha Yagami's user avatar
2 votes

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: ...
DirkT's user avatar
  • 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: ...
Makogan's user avatar
  • 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.
Makogan's user avatar
  • 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" (...
DirkT's user avatar
  • 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 ...
HEKTO's user avatar
  • 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$. ...
Tassle's user avatar
  • 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 ...
HEKTO's user avatar
  • 3,098

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