- NOTE: AT LEAST 12 POINTS REQUIRED TO RUN ALGO.
- Lines: Find the centerpoint region of the current point set on the screen by brute force.
Draw every pair of lines possible and color the centerpoint region green.
- None: Find the centerpoint region of the current point set on the screen by brute force.
Do not draw every pair of lines and color the centerpoint region green.
- Full: Find the centerpoint region of the current point set on the screen by brute force.
Do not draw every pair of lines and color the centerpoint region red.
- Algo: Find a subset of the centerpoint region of the current point set on the screen by the algorithm explained below.
Stop when there are no points in one of the four corner sets.
- Clear: clears the screen and start over.
Source code: Centerpoint
Built with Processing
Algorithm:
We implemented the algorithm in the paper "Computing a Centerpoint of a Finite Planar Set of Points in Linear Time" by Shreesh Jadhav.
Goal:
The goal of the algorithm is to find at least one centerpoint.
Method:
First we find four cuts, L(eft), U(p), D(own), R(ight), according to the following rules
L cut: must have exactly ceiling(n/3)-1 points on the left
U cut: must have exactly ceiling(n/3)-1 points above the cut
ensure in the intersection of L and U there are floor(n/12)-1 points
D cut: must have exactly ceiling(n/3)-1 points below the cut
ensure in the intersection of L and D there are floor(n/12)-1 points
R cut: must have less than ceiling(n/3) points to the right
ensure in the intersection of R and U there at least floor(n/12)-1 points
ensure in the intersection of R and D there at least floor(n/12)-1 points
Now that we have the four cuts, we attempt to prune points.
We grab four distinct points, one from each set UR, UL, DR, DL.
If the four points are in convex position, then we add the radon point of them and remove the four points.
If the four points are not in convex position, we keep the point inside the triangle, and remove the three vertexes of the triangle.
We repeat this process until one of the sets UR, UL, DR, DL is empty.
If one of the sets are empty, then we find new cuts.
The algorithm terminates once the new cuts already have an empty set of UR, UL, DR, DL.
Ocne the algorithm terminates, use a brute force algorithm to determine the centerpoint region.
Runtime:
T(n)=T(3n/4)+O(n) which is T(n)=O(n).
Note:
The region found by this algorithm is smaller than the maximum centerpoint region.