Witness complex

Functions
template<typename KNearestNeighbours , typename Point_random_access_range >
void	Gudhi::witness_complex::landmark_choice_by_furthest_point (Point_random_access_range const &points, int nbL, KNearestNeighbours &knn)
	Landmark choice strategy by iteratively adding the furthest witness from the current landmark set as the new landmark. More...
template<typename KNearestNeighbours , typename Point_random_access_range >
void	Gudhi::witness_complex::landmark_choice_by_random_point (Point_random_access_range const &points, int nbL, KNearestNeighbours &knn)
	Landmark choice strategy by taking random vertices for landmarks. More...
template<class KNearestNeighbors , class SimplicialComplexForWitness >
void	Gudhi::witness_complex::witness_complex (KNearestNeighbors const &knn, int nbL, int dim, SimplicialComplexForWitness &sc)
	Iterative construction of the witness complex. More...

Detailed Description

Author

Siargey Kachanovich

Witness complex representation

Definitions

Witness complex is a simplicial complex defined on two sets of points in :

• set of witnesses and
• set of landmarks.

The simplices are based on landmarks and a simplex belongs to the witness complex if and only if it is witnessed, that is:

is witnessed if there exists a point such that w is closer to the vertices of than other points in and all of its faces are witnessed as well.

The data structure is described in [4] .

Implementation

The principal class of this module is Gudhi::Witness_complex.

In both cases, the constructor for this class takes a {witness}x{closest_landmarks} table, where each row represents a witness and consists of landmarks sorted by distance to this witness. This table can be constructed by two additional classes Landmark_choice_by_furthest_point and Landmark_choice_by_random_point also included in the module.

Running time as function on number of landmarks

Running time as function on number of witnesses for |L|=300

Copyright

GNU General Public License v3.

Function Documentation

template<typename KNearestNeighbours , typename Point_random_access_range >

void Gudhi::witness_complex::landmark_choice_by_furthest_point	(	Point_random_access_range const &	points,
		int	nbL,
		KNearestNeighbours &	knn
	)

Landmark choice strategy by iteratively adding the furthest witness from the current landmark set as the new landmark.

It chooses nbL landmarks from a random access range points and writes {witness}*{closest landmarks} matrix in knn.

The type KNearestNeighbors can be seen as Witness_range<Closest_landmark_range<Vertex_handle>>, where Witness_range and Closest_landmark_range are random access ranges

template<typename KNearestNeighbours , typename Point_random_access_range >

void Gudhi::witness_complex::landmark_choice_by_random_point	(	Point_random_access_range const &	points,
		int	nbL,
		KNearestNeighbours &	knn
	)

Landmark choice strategy by taking random vertices for landmarks.

It chooses nbL distinct landmarks from a random access range points and outputs a matrix {witness}*{closest landmarks} in knn.

The type KNearestNeighbors can be seen as Witness_range<Closest_landmark_range<Vertex_handle>>, where Witness_range and Closest_landmark_range are random access ranges and Vertex_handle is the label type of a vertex in a simplicial complex. Closest_landmark_range needs to have push_back operation.

Examples:

Witness_complex/witness_complex_from_file.cpp, and Witness_complex/witness_complex_sphere.cpp.

template<class KNearestNeighbors , class SimplicialComplexForWitness >

void Gudhi::witness_complex::witness_complex	(	KNearestNeighbors const &	knn,
		int	nbL,
		int	dim,
		SimplicialComplexForWitness &	sc
	)

Iterative construction of the witness complex.

The witness complex is written in simplicial complex sc_ basing on a matrix knn of nearest neighbours of the form {witnesses}x{landmarks}.

The type KNearestNeighbors can be seen as Witness_range<Closest_landmark_range<Vertex_handle>>, where Witness_range and Closest_landmark_range are random access ranges.

Procedure takes into account at most (dim+1) first landmarks from each landmark range to construct simplices.

Landmarks are supposed to be in [0,nbL_-1]

Examples:

Witness_complex/witness_complex_from_file.cpp, and Witness_complex/witness_complex_sphere.cpp.