A practical approach to the 2D incremental nearest-point problem suitable for different point distributions

摘要

In this paper we present a new practical approach to solve the incremental nearest-point problem in the plane. We used the proposed approach in industrial applications with a superior behaviour to the theoretically better solutions. The method efficiently avoids the requirement of initial randomization of the input points by splitting the plane in strips using a heuristic. Points in strips are stored either in (a,b)-skip lists or in (a,b)-trees. Testing of the algorithms at different point distributions shows that our algorithm, using proposed heuristic, is almost insensible to distributions of input points, what makes the algorithm very attractive for various engineering applications.