The maximal distance between imprecise point objects

Abstract

In this paper we propose a new mathematical model of imprecise point objects and a new algorithm for determining the maximal distance between imprecise point objects. Results obtained with our model can be used in various applications, such as GIS (imprecise spatial object modelling), robotics (environment models), and image analysis (imprecise feature extraction). Imprecise point objects are modelled as fuzzy points in linear fuzzy space. Linear fuzzy space is defined over Rn, where the membership function is convex, upper semi-continuous, symmetric w.r.t. the core and linearly decreasing w.r.t. the core distance, where the core is a single point. A fuzzy convex hull is defined in linear fuzzy space. The distance between objects/points is modelled as an imprecise point object in linear fuzzy space defined over R1. Fuzzy ordering relations are defined in distance space. The maximal distance is a fuzzy set over a set of distances. The maximal distance between a set of imprecise point objects is then determined as the maximal distance of fuzzy convex hull edge points. An algorithm for determining the maximal distance between imprecise points belonging to one- and two-dimensional linear fuzzy space is given. For an exact calculation of this maximal distance, computational complexity of the algorithm is of polynomial growth of the fourth degree. However, if the maximal distance is determined approximately, then the algorithms' computational complexity is of power growth of the quadratic degree with respect to the cardinality of the convex edge. © 2010 Elsevier B.V. All rights reserved.