typedef enum {
    IGRAPH_METRIC_EUCLIDEAN = 0,
    IGRAPH_METRIC_L2 = IGRAPH_METRIC_EUCLIDEAN,
    IGRAPH_METRIC_MANHATTAN = 1,
    IGRAPH_METRIC_L1 = IGRAPH_METRIC_MANHATTAN
} igraph_metric_t;

Values: 

igraph_error_t igraph_delaunay_graph(igraph_t *graph, const igraph_matrix_t *points);

This function constructs the graph corresponding to the Delaunay triangulation of an n-dimensional spatial point set.

The current implementation uses Qhull.

Reference:

Barber, C. Bradford, David P. Dobkin, and Hannu Huhdanpaa. The Quickhull Algorithm for Convex Hulls. ACM Transactions on Mathematical Software 22, no. 4 (1996): 469–83. https://doi.org/10.1145/235815.235821.

Arguments: 

Returns: 

Time complexity: According to Theorem 3.2 in the Qhull paper, O(n log n) for d <= 3 and O(n^floor(d/2) / floor(d/2)!) where n is the number of points and d is the dimensionality of the point set.

igraph_error_t igraph_nearest_neighbor_graph(igraph_t *graph,
        const igraph_matrix_t *points,
        igraph_metric_t metric,
        igraph_int_t k,
        igraph_real_t cutoff,
        igraph_bool_t directed);

This function constructs the k nearest neighbor graph of a given point set. Each point is connected to at most k spatial neighbors within a radius of cutoff.

Arguments: 

Returns: 

Time complexity: O(n log(n)) where n is the number of points.

igraph_error_t igraph_gabriel_graph(igraph_t *graph, const igraph_matrix_t *points);

In the Gabriel graph of a point set, two points A and B are connected if there is no other point C within the closed ball of which AB is a diameter. The Gabriel graph is connected, and in 2D it is planar. igraph supports computing the Gabriel graph of arbitrary dimensional point sets.

The Gabriel graph is a special case of lune-based and circle-based β-skeletons with β=1.

Arguments: 

Returns: 

See also: 

Time Complexity: Around O(n^floor(d/2) log n), where n is the number of points and d is the dimensionality of the point set.

igraph_error_t igraph_relative_neighborhood_graph(igraph_t *graph, const igraph_matrix_t *points);

The relative neighborhood graph is constructed from a set of points in space. Two points A and B are connected if and only if there is no other point C so that AC < AB and BC < AB, with the inequalities being strict.

Most authors define the relative neighborhood graph to coincide with a lune-based β-skeleton for β = 2. In igraph, there is a subtle difference: the β = 2 skeleton connects points A and B when there is no point C so that AC <= AB and BC <= AB. Therefore, three points forming an equilateral triangle are connected in the relative neighborhood graph, but disconnected in the β = 2 skeleton.

With these definitions, the relative neighborhood graph is always connected, while the β = 2 skeleton is always triangle-free.

Arguments: 

Returns: 

See also: 

Time Complexity: Around O(n^floor(d/2) log n), where n is the number of points and d is the dimensionality of the point set.

igraph_error_t igraph_lune_beta_skeleton(igraph_t *graph, const igraph_matrix_t *points, igraph_real_t beta);

This function constructs the lune-based β-skeleton of an n-dimensional spatial point set.

A larger β results in a larger region, and a sparser graph. Values of β < 1 are only supported in 2D, and are considerably slower.

The Gabriel graph is a special case of beta skeleton where β = 1.

The Relative Neighborhood graph is a special case of beta skeleton where β approaches

Arguments: 

Returns: 

Time Complexity: Around O(n^floor(d/2) log n), where n is the number of points and d is the dimensionality of the point set.

igraph_error_t igraph_circle_beta_skeleton(igraph_t *graph, const igraph_matrix_t *points, igraph_real_t beta);

This function constructs the circle based β-skeleton of a 2D spatial point set.

A larger beta value results in a larger region, and a sparser graph. Values of beta < 1 are considerably slower

Arguments: 

Returns: 

Time Complexity: Around O(n^floor(d/2) log n), where n is the number of points and d is the dimensionality of the point set.

igraph_error_t igraph_beta_weighted_gabriel_graph(
    igraph_t *graph,
    igraph_vector_t *weights,
    const igraph_matrix_t *points,
    igraph_real_t max_beta);

This function generates a Gabriel graph, and for each edge of this graph it computes the threshold β value at which the edge ceases to be part of the lune-based β-skeleton. For edges that continue to be part of β-skeletons for arbitrarily large β, IGRAPH_INFINITΥ is returned.

The max_beta cutoff parameter controls the largest β value to consider For edges that persist above this β value, IGRAPH_INFINITΥ is returned. This parameter serves to improve performance: the smaller this cutoff, the faster the computation. Pass IGRAPH_INFINITY to use no cutoff.

Arguments: 

Returns: 

See also: 

Time Complexity: Around O(n^floor(d/2) log n), where n is the number of points and d is the dimensionality of the point set. Though large values of max_beta can cause long run times if there are edges that disappear only at large betas.

igraph_error_t igraph_spatial_edge_lengths(
        const igraph_t *graph,
        igraph_vector_t *lengths,
        const igraph_matrix_t *points,
        igraph_metric_t metric);

The length of each edge is computed based on spatial coordinates. The length can be employed by several igraph functions, such as igraph_voronoi(), igraph_betweenness(), igraph_closeness() and others.

Arguments: 

Returns: 

See also: 

Time complexity: O(|E| d) where |E| is the number of edges and d is the dimensionality of the point set.

igraph_error_t igraph_convex_hull_2d(
        const igraph_matrix_t *data,
        igraph_vector_int_t *resverts,
        igraph_matrix_t *rescoords);

The convex hull is determined by the Graham scan algorithm. See the following reference for details:

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0262032937. Pages 949-955 of section 33.3: Finding the convex hull.

Arguments: 

Returns: 

Time complexity: O(n log(n)) where n is the number of vertices.