 |
 |
|
|
Input Description: A polygon or polyhedron \(p\), with \(n\) vertices.
Problem: Find a polygon or polyhedron \(p'\) with \(n'\) vertices, where the shape of \(p'\) is close to \(p\) while \(n' << n\).
Excerpt from The Algorithm Design Manual: Polygon simplification has two primary applications. The first is in cleaning up a noisy representation of a polygon, perhaps obtained by scanning a picture of an object. By processing it, we hope to remove the noise and reconstruct the original object. The second is in data compression, where given a large and complicated object, we seek to simplify it by reducing detail. Ideally, we obtain a polygon with far fewer vertices that looks essentially the same. This can be a big win in computer graphics, where replacing a large model with a smaller model might have little visual impact but be significantly faster to render.
  Convex Hull |
  Discrete Fourier Transform |
  Minkowski Sum |
As an Amazon affiliate, I earn from qualifying purchases if you buy from links on this website.
Computational Geometry : Algorithms and Applications by Mark De Berg, Marc Van Kreveld, Mark Overmars, and O. Schwartskopf
Computational Geometry in C by Joseph O'Rourke
Discrete Voronoi Skeletons by R. Ogniewicz