From 478642224bca43ebe2c878159fb5b7989ed2641e Mon Sep 17 00:00:00 2001
From: Arnur Nigmetov <a.nigmetov@gmail.com>
Date: Thu, 6 Apr 2017 11:54:54 +0200
Subject: Heuristic for bottleneck: estimate on sampled diagram

Sample input diagrams and use the distance between samples as initial guess
in binary search.

Relevant variables:
bottleneck_dist.cpp:10 useSamplingHeur (if false, heuristic is never applied)
bottleneck_dist.cpp:11 heurThreshold (heuristic is not applid to diagrams with
        fewer points)
TODO: add command-line parameters instead

Sampling strategy: sort points by multiplicity, set cutting value to be
the multiplicity where the increase of the next one is maximal and only keep
points whose multiplicity is less then the cutting value
---
 geom_bottleneck/bottleneck/include/bottleneck.h | 15 +++++++++++++++
 1 file changed, 15 insertions(+)

(limited to 'geom_bottleneck/bottleneck/include/bottleneck.h')

diff --git a/geom_bottleneck/bottleneck/include/bottleneck.h b/geom_bottleneck/bottleneck/include/bottleneck.h
index 2078965..75c902f 100644
--- a/geom_bottleneck/bottleneck/include/bottleneck.h
+++ b/geom_bottleneck/bottleneck/include/bottleneck.h
@@ -46,6 +46,10 @@ typedef std::pair<double, std::pair<size_t, size_t>> DistVerticesPair;
 // b) if the interval is not (0,0), then  (distMax - distMin) / distMin < epsilon 
 std::pair<double, double> bottleneckDistApproxInterval(DiagramPointSet& A, DiagramPointSet& B, const double epsilon);
 
+
+// heuristic (sample diagram to estimate the distance)
+std::pair<double, double> bottleneckDistApproxIntervalHeur(DiagramPointSet& A, DiagramPointSet& B, const double epsilon);
+
 // get approximate distance,
 // see bottleneckDistApproxInterval
 double bottleneckDistApprox(DiagramPointSet& A, DiagramPointSet& B, const double epsilon);
@@ -74,6 +78,17 @@ std::pair<double, double> bottleneckDistApproxInterval(PairContainer& A, PairCon
     return bottleneckDistApproxInterval(a, b, epsilon);
 }
 
+
+template<class PairContainer>
+double bottleneckDistApproxHeur(PairContainer& A, PairContainer& B, const double epsilon)
+{
+    DiagramPointSet a(A.begin(), A.end());
+    DiagramPointSet b(B.begin(), B.end());
+    std::pair<double,  double> resPair = bottleneckDistApproxIntervalHeur(a, b, epsilon);
+    return resPair.second;
+}
+
+
 // get approximate distance,
 // see bottleneckDistApproxInterval
 template<class PairContainer>
-- 
cgit v1.2.3