Curves, points, incidences and covering
By: Arijit Bishnu, Mathew Francis, Pritam Majumder
Potential Business Impact:
Finds fewest lines to connect all dots.
Given a point set, mostly a grid in our case, we seek upper and lower bounds on the number of curves that are needed to cover the point set. We say a curve covers a point if the curve passes through the point. We consider such coverings by monotonic curves, lines, orthoconvex curves, circles, etc. We also study a problem that is converse of the covering problem -- if a set of $n^2$ points in the plane is covered by $n$ lines then can we say something about the configuration of the points?
Similar Papers
Curves, points, incidences and covering
Combinatorics
Finds fewest lines to connect dots.
Covering half-grids with lines and planes
Combinatorics
Finds fewer lines to cover points.
Covering Complete Geometric Graphs by Monotone Paths
Combinatorics
Connects dots with paths, fewer than expected.