Computational Geometry on the Grid: Traversal and Planesweep Algorithms for Spatial Applications

Introduction Numerical robustness, topological correctness, reliability, accuracy, and simultaneously efficiency of geometric algorithms are fundamental requirements for spatial predicates and operations in spatial database systems, geographical information systems, VLSI design, CAD, and many other related application areas. Although (theoretical) computational geometry has provided a large number of useful and efficient geometric algorithms, we encounter the problem that it is based on Euclidean geometry and infinite-precision arithmetic (real numbers) and that it ignores the reality of a finiteprecision arithmetic (floating point numbers) in computers. Thus, theoretically correct geometric algorithms are not necessarily practically valid. The knowledge about this problem has raised growing interest in solving issues of computational geometry in a discrete space on a uniform integer grid. That is, points, end points of line segments, vertices of polygons, etc. have integer i