Digital hyperplane recognition in arbitrary fixed dimension within an algebraic computation model

摘要

In this paper we present an algorithm for the integer linear programming (ILP) problem within an algebraic model of computation and use it to solve the following digital plane segment recognition problem: Given a set of points M={p1,p2,…,pm}⊆Rn, decide whether M is a portion of a digital hyperplane and, if so, determine its analytical representation. In our setting p1, p2,  …, pm may be arbitrary points (possibly, with rational and/or irrational coefficients) and the dimension n may be any arbitrary fixed integer. We reduce this last problem to an ILP to which our general integer programming algorithm applies. It performs O(m log D) arithmetic operations, where D is a bound on the norm of the domain elements. For the special case of problem dimension two, we propose an elementary algorithm that takes advantage of the specific geometry of the problem and appears to be optimal. It implies an efficient algorithm for digital line segment recognition.