crossing¶

Module used to count the number of crossings in the complete geometric graph

crossing.count_crossings(pts)¶

Returns the he number of crossings in the complete geometric graph with vertex set pts. Runs in O(n^2logn) time.

crossing.count_crossings_candidate_list_py(point_index, candidate_list, pts)¶

Let k=len(candidate_list), n=len(pts). Returns the best candidate for pts[point_index] in time O(n^2logn)+O(k*nlogn).

crossing.count_halving_lines(pts)¶

Counts the number of $lfoor n/2 floor$ k-edges

crossing.count_k_edges(pts, k)¶

Returns the number of k edges in the point set pts

crossing.cr_remove_point(pts)¶

For every point pts[i] in the point set pts, returns an array whose i-th element is the crossing number of pts-pts[i]. In runs in O(n^2 log n) time.

crossing.k_edges_vector(pts)¶

Returns the vector of the number of k edges in the point set pts