NAME

Math::Vector::Real::Farthest - Find the two more distant vectors from a set

SYNOPSIS

use Math::Vector::Real::Farthest;
my ($d2, $v0, $v1) = Math::Vector::Real::Farthest->find(@vs);

DESCRIPTION

This module implements several algorithms for finding the maximum distance between any two vectors from a given set (AKA the set diameter) and some two vectors that are that far away.

METHODS

The methods available are as follows:

($d2, $v0, $v1) = Math::Vector::Real::Farthest->find(@vs)

Returns the square of the maximum distance between any two vectors on the given set (AKA the set diameter squared) and some two vectors which are actually that far away.

The algorithm used in this method is quite similar to the one described in "A Practical Approach for Computing the Diameter of a Point-Set", SOCG_2001, Sariel Har-Peled. The main difference being that, when dividing the subset in some tree node along the largest side of the wrapping box, instead of doing it at the middle point it does it at the median.

The global $Math::Vector::Real::Farthes::threshold_brute_force defines the subset size at which the algorithm switches to the brute-force algorithm (which is more efficient for small data sizes).

($d2, $v0, $v1) = Math::Vector::Real::Farthest->find_brute_force(@vs)

This is an alternative implementation of find that uses the brute force algorithm.

The find method already switches automatically to the brute force algorithm when the number of vectors is low.

This method is provided just for testing purposes. Though, note that the vectors returned by find and find_brute_force for the same given set may be different.

($d2, $v0, $v1) = Math::Vector::Real::Farthest->find_2d_convex_hull

In order to calculate the diameter of a set of bidimensional vectors, an algorithm commonly recommended on the literature is to calculate the convex hull of the set and then to use the rotating-calipers method to find the two more distant vectors from it. This method implements that algorithm.

Benchmarks show that the generic algorithm used by find is usually much faster.

See also the Wikipedia entries for convex hull and rotating calipers.

In order to use this method the extra module Sort::Key::Radix must be also installed.

If this module is not fast enough for you, tell me. Maybe in a happy day I could write a C/XS version.

SEE ALSO

Math::Vector::Real.

I have found two papers describing efficient algorithms for solving the set diameter problem. One is "A Practical Approach for Computing the Diameter of a Point-Set", SOCG_2001, Sariel Har-Peled; the other "Computing the Diameter of a Point Set", INRIA 2001, Malandain, Grégoire and Boissonnat, Jean-Daniel (the links to the paper are dead, but Google is able to find the file, look for dgci-2002.ps.gz).

Note that the source code for Math::Vector::Real::Farthest is not based on the code provided with those papers.

COPYRIGHT AND LICENSE

Copyright (C) 2014 by Salvador Fandiño <sfandino@yahoo.com>.

This library is free software; you can redistribute it and/or modify it under the same terms as Perl itself, either Perl version 5.18.2 or, at your option, any later version of Perl 5 you may have available.