Here are the publications related to PyDCG by their respective module.
- crossing
- Computational search of small point sets with small rectilinear crossing number. Ruy Fabila-Monroy and Jorge Lopez.
- Algoritmo amortizado para el número de cruces rectilíneos sobre gráficas completas (in Spanish). Frank Duque.
- holes
-
Searching for Empty Convex Polygons.
David P. Dobkin, Herbert Edelsbrunner and Mark H. Overmars
In that paper the authors give an algorithm to compute the number of \(r\)-holes in a given point set in time proportional to the number of these holes.
- Un algoritmo para contar polígonos convexos vacíos en conjuntos de puntos en el plano (in Spanish). Carlos Hidalgo-Toscano.
- points
- Enumerating order types for small point sets with applications. O. Aichholzer, F. Aurenhammer, and H. Krasser.
- Drawing the double circle on
a grid of minimum size.
Sergey Bereg, Ruy Fabila-Monroy, David Flores-Peñaloza, Mario Lopez, Pablo Pérez-Lantero
We describe an algorithm to generate the double circle; it runs in linear time. This generator is available in the points module.
Let \( S \) be a set of \( n \) points in the plane. Join every pair of points with a line segment and count the number of pairs of segments that cross. This is the rectilinear crossing number of \( S \). Let \( \overline{cr}(n) \) be the minimum of this value over all sets of \( n \) points in general position in the plane. The rectilinear crossing number project page, keeps track of the progress in determining the rectilinar crossing number. PyDCG has a crossing module that contains various functions for playing with the rectilinear crossing number.
In that paper we used the crossing module to find set of 75 points with only 450492 crossings. There exists a construction that given a point set with few crossing creates larger and larger sets with few crossings. With our set of 75 points were able to break the asymptotic upper bound. As of today, it stands at \( \overline{cr}(n) \le 0.380473 \binom{n}{4}+\Theta (n^3) \).
Frank's Master's thesis. It details an algorithm that receives a set of \(n\) points \(S\), a point \(q \in S \), and a set \(C\) of \(m\) candidate points. The algorithm computes the crossing number of \( S-q+p\) for each \(p \in C \) in \(O((n+m)^2)\) (actually the implementation runs in \(O((n+m)^2 \log (n+m))\) time). If \(m=\Theta(n)\) this is \(O(n)\) per candidate point. The idea was to find a "good" replacement for \(q\) in order to improve the crossing number of \(S\). We found a lot of new sets but none was good enough to give a new asymptotic upper bound. The thesis also contains an algorithm that computes the crossing number of every set of the form \(S-p\) with \(p \in S\) in \(O(n^2)\) total time (again the implementation runs in \(O(n^2 \log n)\) time); the idea is to use this algorithm to use a good set to find good smaller sets. Both algorithms are in the crossing module.
An \(r\)-hole of \(S\) is a subset \(H\) of \(S\), of \(r\) points, that is in convex position and contains no other point of \(S\) in its convex hull. Holes are related to the Happy Ending Problem.
Carlos's Bachelor's thesis; it details the implementation of the above algorithm. The following algorithm is also described: given a point \(q\) not in \(S\) and a point \(p\) computes the number of holes in \(S-p+q\). This is done in time proportional to the number of holes that contain \(p\) and \(q\). Both algorithms are implemented in the holes module.
This module implements various point set generators. It also gives wrappers to the Order Type Database.
The order type is a notion of combinatorial equivalence of point sets. The order type database contains a representative of each equivalence class for \( n=1,\dots,11 \). The points module provides acces to this database.