A kd-tree algorithm to discover the boundary of a black box hypervolume

作者：Rouquier Jean Baptiste; Alvarez Isabelle^*; Reuillon Romain; Wuillemin Pierre Henri

来源：Annals of Mathematics and Artificial Intelligence, 2015, 75(3-4): 335-350.

DOI：10.1007/s10472-015-9456-8

• Kd-tree
• Approximation of hyper-volume
• Viability
• Decision support system

In the framework of Decision Support Systems, mathematical viability theory can be used to classify the states and the trajectories of a dynamical system evolving in a set of desirable states. Since obtaining this viability theory output is a complex and computationally intensive task, we propose in this article to consider a compact representation of this set and its approximations using kd-trees. Given a subset of R-n of non null measure, defined through a black box an oracle), and assuming some regularity properties on this set, we build a kd-tree based data structure representing this set, which can be used as an input to the viability algorithm. This data structure has a complexity close to gaining one dimension, both in terms of space and in number of calls to the oracle, compared to the exhaustive computation on a regular grid. This data structure produces a characteristic i.e. a function that can be used in lieu of the oracle), allows to measure the volume of the set, and to compute the distance to the boundary of the set for any point. It offers distance guarantee between the points of the original set and its kd-tree approximation.

• 出版日期2015-12