Accéder directement au contenu Accéder directement à la navigation
Article dans une revue

A kd-tree algorithm to discover the boundary of a black box hypervolume or how to peel potatoes by recursively cutting them in halves

Abstract : Given a subset of $\R^\ndim$ of non-zero measure, defined through a blackbox function (an oracle), and assuming some regularity properties on this set, we build an efficient data structure representing this set. The naive approach would consists in sampling every point on a regular grid. As compared to it, our data structure has a complexity close to gaining one dimension both in terms of space and in number of calls to the oracle. This data structure produces a characteristic function (i.e. a function that can be used in lieu of the oracle), allows to measure the volume of the set, and allows to compute the distance to the boundary of the set for any point.
Type de document :
Article dans une revue
Liste complète des métadonnées

Littérature citée [10 références]  Voir  Masquer  Télécharger

https://hal.archives-ouvertes.fr/hal-00816704
Déposant : Isabelle Alvarez <>
Soumis le : lundi 22 avril 2013 - 17:39:57
Dernière modification le : mardi 22 septembre 2020 - 03:55:42
Archivage à long terme le : : mardi 23 juillet 2013 - 04:14:41

Fichier

mainPotatoe.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Jean-Baptiste Rouquier, Isabelle Alvarez, Romain Reuillon, Pierre-Henri Wuillemin. A kd-tree algorithm to discover the boundary of a black box hypervolume or how to peel potatoes by recursively cutting them in halves. Annals of Mathematics and Artificial Intelligence, Springer Verlag, 2015, 75 (3), pp.335-350. ⟨10.1007/s10472-015-9456-8⟩. ⟨hal-00816704⟩

Partager

Métriques

Consultations de la notice

1036

Téléchargements de fichiers

878