On finite-precision representations of geometric objects

摘要

The paper presents an experimental study on approximation of continuously distributed geometric objects by equations with integer coefficients. The problem considered here is, given an equation of a geometric object with real coefficients, to find a set of integer coefficients that gives a good approximation to the original equation. This problem is reduced to a problem called a simultaneous Diophantine approximation problem, for which no efficient method to give the best solution has yet been found. Here considered are three heuristic methods: a naive method, a method based on the continued fraction theory, and a method using the basis reduction technique. These methods together with a brute-force exhaustive search method are studied using randomly generated data, and also proposed is a hybrid method, which seems allowable from both the viewpoint of time complexity and the viewpoint of quality of approximation.