[mlpack-git] master: Removed the property that each child bound is contained entirely in the parent bound. (add74d0)

[gitdub at mlpack.org]

Repository : https://github.com/mlpack/mlpack
On branch  : master
Link       : https://github.com/mlpack/mlpack/compare/acd81e11579f69e75aa8406b2982328c88cf1fde...1e9f0f39ea4443f0d595c395871ea8c6b27443af

>---------------------------------------------------------------

commit add74d0ea472287a58472cd8cb2573b3bf7a7af8
Author: Mikhail Lozhnikov <lozhnikovma at gmail.com>
Date:   Sat Aug 6 21:12:23 2016 +0300

    Removed the property that each child bound is contained entirely in the parent bound.


>---------------------------------------------------------------

add74d0ea472287a58472cd8cb2573b3bf7a7af8
 .../vantage_point_tree/vantage_point_tree_impl.hpp | 19 --------------
 src/mlpack/tests/vantage_point_tree_test.cpp       | 29 ++++++++++++++++++----
 2 files changed, 24 insertions(+), 24 deletions(-)

diff --git a/src/mlpack/core/tree/vantage_point_tree/vantage_point_tree_impl.hpp b/src/mlpack/core/tree/vantage_point_tree/vantage_point_tree_impl.hpp
index ffba3ec..fc5c571 100644
--- a/src/mlpack/core/tree/vantage_point_tree/vantage_point_tree_impl.hpp
+++ b/src/mlpack/core/tree/vantage_point_tree/vantage_point_tree_impl.hpp
@@ -680,15 +680,6 @@ void VantagePointTree<MetricType, StatisticType, MatType, BoundType, SplitType>:
   if (count > 0)
     bound |= dataset->cols(begin, begin + count - 1);
 
-  VantagePointTree* tree = this;
-
-  while (tree->Parent() != NULL)
-  {
-    tree->Parent()->Bound() |= tree->Bound();
-    tree->Parent()->furthestDescendantDistance = 0.5 *
-			tree->Parent()->Bound().Diameter();
-    tree = tree->Parent();
-  }
   // Calculate the furthest descendant distance.
   furthestDescendantDistance = 0.5 * bound.Diameter();
 
@@ -763,16 +754,6 @@ SplitNode(std::vector<size_t>& oldFromNew,
   if (count > 0)
     bound |= dataset->cols(begin, begin + count - 1);
 
-  VantagePointTree* tree = this;
-
-  while (tree->Parent() != NULL)
-  {
-    tree->Parent()->Bound() |= tree->Bound();
-    tree->Parent()->furthestDescendantDistance = 0.5 *
-			tree->Parent()->Bound().Diameter();
-    tree = tree->Parent();
-  }
-
   // Calculate the furthest descendant distance.
   furthestDescendantDistance = 0.5 * bound.Diameter();
 
diff --git a/src/mlpack/tests/vantage_point_tree_test.cpp b/src/mlpack/tests/vantage_point_tree_test.cpp
index 696313a..fe7cb42 100644
--- a/src/mlpack/tests/vantage_point_tree_test.cpp
+++ b/src/mlpack/tests/vantage_point_tree_test.cpp
@@ -130,11 +130,21 @@ BOOST_AUTO_TEST_CASE(HollowBallBoundTest)
 template<typename TreeType>
 void CheckBound(TreeType& tree)
 {
+  typedef typename TreeType::ElemType ElemType;
   if (tree.IsLeaf())
   {
+    // Ensure that the bound contains all descendant points.
     for (size_t i = 0; i < tree.NumPoints(); i++)
-      BOOST_REQUIRE_EQUAL(true,
-          tree.Bound().Contains(tree.Dataset().col(tree.Point(i))));
+    {
+      ElemType dist = tree.Bound().Metric().Evaluate(tree.Bound().Center(),
+        tree.Dataset().col(tree.Point(i)));
+
+      BOOST_REQUIRE_LE(tree.Bound().InnerRadius(), dist  *
+          (1.0 + 10.0 * std::numeric_limits<ElemType>::epsilon()));
+
+      BOOST_REQUIRE_LE(dist, tree.Bound().OuterRadius() *
+          (1.0 + 10.0 * std::numeric_limits<ElemType>::epsilon()));
+    }
   }
   else
   {
@@ -145,9 +155,18 @@ void CheckBound(TreeType& tree)
     BOOST_REQUIRE_EQUAL(central->Bound().InnerRadius(), 0.0);
     BOOST_REQUIRE_EQUAL(central->Bound().OuterRadius(), 0.0);
 
-    BOOST_REQUIRE_EQUAL(tree.Bound().Contains(tree.Central()->Bound()), true);
-    BOOST_REQUIRE_EQUAL(tree.Bound().Contains(tree.Inner()->Bound()), true);
-    BOOST_REQUIRE_EQUAL(tree.Bound().Contains(tree.Outer()->Bound()), true);
+    // Ensure that the bound contains all descendant points.
+    for (size_t i = 0; i < tree.NumDescendants(); i++)
+    {
+      ElemType dist = tree.Bound().Metric().Evaluate(tree.Bound().Center(),
+        tree.Dataset().col(tree.Descendant(i)));
+
+      BOOST_REQUIRE_LE(tree.Bound().InnerRadius(), dist  *
+          (1.0 + 10.0 * std::numeric_limits<ElemType>::epsilon()));
+
+      BOOST_REQUIRE_LE(dist, tree.Bound().OuterRadius() *
+          (1.0 + 10.0 * std::numeric_limits<ElemType>::epsilon()));
+    }
 
     CheckBound(*tree.Inner());
     CheckBound(*tree.Outer());