Computational geometry designs and analyzes algorithms for geometric objects represented by coordinates or combinatorial structure. Problems include finding a convex hull, intersecting segments and locating points in a subdivision. The representation and numerical predicates are part of correctness, not merely implementation details.
For points in the plane, the orientation predicate uses the sign ofA positive sign places to the left of the directed line from to ; zero means collinearity. The points give a positive determinant. Near-collinear inputs can make round-off error reverse the sign and corrupt an algorithm's combinatorial decisions. Shewchuk's adaptive predicates increase arithmetic precision only as needed to certify the correct sign.[ref]
Articles by others on the same topic
Computational geometry is a branch of computer science and mathematics that deals with the study of geometric objects and their interactions using computational techniques. It focuses on the development of algorithms and data structures for solving geometric problems, which can involve points, lines, polygons, polyhedra, and more complex shapes in various dimensions.