Function

Static Public Summary
public	clarkson(prec: function, a: any[], i: number, j: number): number Output sensitive inplace algorithm to find the minima set of a set S of elements according to some partial order.

Static Public

public clarkson(prec: function, a: any[], i: number, j: number): number source

import clarkson from '@partial-order/poset/src/minima/clarkson.js'

Output sensitive inplace algorithm to find the minima set of a set S of elements according to some partial order.

Uses at most 3nA comparisons where A is the cardinality of the minima set.

For (1), at most nA comparisons are used since we compare each element of S with each elements of the minima set which is of cardinality at most A during the execution of the algorithm.

For (2), for each executed loop we obtain a new minimum and increase the size of the constructed minima set by 1, hence there are at most A loops execution, each of which loops over at most n elements. (2) uses thus at most nA comparisons.

The running time is dominated by the comparison time and thus the complexity of this algorihtm is O(nA).

Description and context in

More Output-Sensitive Geometric Algorithms. -------------------- Kenneth L. Clarkson -

Params:

Name	Type	Attribute	Description
prec	function		relation
a	any[]		input array
i	number		inclusive left bound of the input
j	number		non-inclusive right bound of the input

Return:

number

non-inclusive right bound of the minima set