9 #include "Sampling.cpp"
13 #include "EuclideanSpace.hpp"
14 #include "KMedian.hpp"
33 template<
typename InputIterator>
42 template<
typename InputIterator>
46 template<
typename InputIterator>
47 std::unique_ptr<std::vector<Point>> constructSatisfyingSet(InputIterator begin, InputIterator end,
double eps,
size_t sizeOfRandomSample);
49 template<
typename InputIterator>
50 std::unique_ptr<std::vector<Point>> constructSatisfyingSet(InputIterator begin, InputIterator end,
double a,
double b,
double eps,
size_t sizeOfRandomSample);
52 std::unique_ptr<std::vector<Point>> constructGridSphere(std::vector<Point>
const & basis,
Point basePoint,
double sideLength,
double radius);
60 template<
typename InputIterator>
65 int dim = begin->getDimension();
80 for(
int i = 0; i < rounds; ++i)
83 std::unique_ptr<std::vector<Point>> samSet(Sampling::sampleWithoutReplacementFast<InputIterator, Point>(begin, end, 1000));
84 double tmpCost(kmedian.
cost(samSet->begin(), samSet->end(), tmpPoint));
85 if(tmpCost < cost || i == 0)
94 template<
typename InputIterator>
98 size_t sampleSize = 1;
99 std::unique_ptr<std::vector<Point>> satSet(constructSatisfyingSet(begin, end, eps, sampleSize));
100 std::unique_ptr<std::vector<Point>> samSet(Sampling::sampleWithoutReplacementFast<InputIterator, Point>(begin, end, 10));
104 for(
size_t i = 0; i < satSet->size(); ++i)
106 double tmpcost = kmedian.
cost(samSet->begin(), samSet->end(), (*satSet)[i]);
107 if(tmpcost < cost || i == 0)
110 median = (*satSet)[i];
117 template<
typename InputIterator>
118 std::unique_ptr<std::vector<Point>> KumarMedian::constructSatisfyingSet(InputIterator begin, InputIterator end,
double eps,
size_t sizeOfRandomSample)
120 std::unique_ptr<std::vector<Point>> sample(Sampling::sampleWithoutReplacementFast<InputIterator, Point>(begin, end, std::ceil(1.0/eps+1.0)));
121 double v = kmedian.
cost(sample->begin()+1, sample->end(), (*sample)[0]);
123 double a = v * std::pow(eps, 3) / 2;
127 std::unique_ptr<std::vector<Point>> set(constructSatisfyingSet(sample->begin()+1, sample->end(), a, b, eps, sizeOfRandomSample));
128 set->push_back((*sample)[0]);
133 std::unique_ptr<std::vector<Point>> set(
new std::vector<Point>(sample->begin(), sample->begin()+1));
138 template<
typename InputIterator>
139 std::unique_ptr<std::vector<Point>> KumarMedian::constructSatisfyingSet(InputIterator begin, InputIterator end,
double a,
double b,
double eps,
size_t sizeOfRandomSample)
141 std::unique_ptr<std::vector<Point>> sampleVector(Sampling::sampleWithoutReplacementFast<InputIterator, Point>(begin, end, sizeOfRandomSample));
142 int lowerBound(std::floor(std::log(eps/4.0*a)));
143 int upperBound(std::ceil(std::log(b)));
144 std::unique_ptr<std::vector<Point>> basis(space.orthonormalize(sampleVector->begin(), sampleVector->end()));
146 std::unique_ptr<std::vector<Point>> satisfyingSet(
new std::vector<Point>());
147 for(
auto it = sampleVector->begin(); it != sampleVector->end(); ++it)
149 for(
int i = lowerBound; i <= upperBound; ++i)
151 double t = std::pow(2, i);
152 std::unique_ptr<std::vector<Point>> subset = constructGridSphere(*basis, *it, (eps*t)/(4.0*sampleVector->size()), 2.0*t);
153 satisfyingSet->insert(satisfyingSet->end(), subset->begin(), subset->end());
157 return satisfyingSet;