Finite-Resolution Computational Geometry

Geometric algorithms are usually designed with continuous parameters in mind. When the underlying geometric space is intrinsically discrete, as is the case for computer graphics problems, such algorithms are apt to give invalid solutions if properties of a finite-resolution space are not taken into account. In this paper we discuss an approach for transforming geometric concepts and algorithms from the continuous domain to the discrete domain. As an example we consider the discrete version of the problem of finding all intersections of a collection of line segments. We formulate criteria for a satisfactory solution to this problem, and design an interface between the continuous domain and the discrete domain which supports certain invariants. This interface enables us to obtain a satisfactory solution by using plane-sweep and a variant of the continued fraction algorithm.

Authors

• Daniel H. Greene
• F. Frances Yao

Keywords

• Computational geometry
• Computer graphics
• Topology
• Algorithm design and analysis
• Concrete
• Solid modeling
• Application software
• Finite Resolution
• Line Segment
• Discrete Domain
• Satisfactory Solution
• Continuous Domain
• Continued Fraction
• Geometric Algorithm
• Denominator
• Grid Points
• Shortest Path
• Original Line
• Base Line
• Nearest Point
• Intersection Of Line
• Side Of Line
• Lattice Points
• Rational Numbers
• Collection Of Lines
• Strictly Decreasing
• Number Theory
• Unit Square