Symbolic Computation Group

Soft Geometric Computation is a numerical, certified approach to designing geometric algorithms with guaranteed topological properties. "Softness" here is contrasted to "hard" approaches that are traditionally associated with exact algorithms. Barriers to "hard" approaches include high complexity and the non-existence of hard solutions. Many soft solutions are practical with adaptive complexity. We describe conceptual as well as computational tools to support soft algorithms. These ideas are framed in the classic subdivision framework. We illustrate the ideas in areas such as root isolation and clustering, robot motion planning, Voronoi diagrams and surface meshing.