Curves, points, incidences and covering

Arijit Bishnu, Mathew Francis, Pritam Majumder · 2025

Read Curves, points, incidences and covering by Arijit Bishnu, Mathew Francis, Pritam Majumder (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-21758.txt.

Introduction

Arijit Bishnu, Mathew Francis, and Pritam Majumder wrote a 2025 paper on covering point sets with curves. A curve covers a point when it passes through it. Given a field of points, often a grid, how few curves of a set kind can thread them all?

The team sets upper and lower bounds for that count across curve kinds: rising curves, straight lines, box shaped curves, and circles. A converse puzzle joins the work. If a grid of n squared points is threaded by just n lines, what must the point layout look like? Such bounds tie into wider work on how often points and curves can meet.

Catalog record

CREATORArijit Bishnu, Mathew Francis, Pritam Majumder
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE47 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-21758

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Curves, points, incidences and covering Arijit Bishnu, Mathew Francis, Pritam Majumder Abstract 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 n^{2} points in the plane is covered by n n lines then can we say something about the configuration of the points? Keywords : Discrete geometry, Combinatorial geometry, Incidence. 1 Introduction Let C be a family of curves (e.g., circle, convex curves, etc.) and P be a set of points in \mathbb{R}^{d} . A curve c\in C covers a point p\in P if p lies on the curve c . We say that C covers P if all points in P are covered by the union \bigcup C of all members of C . We will be interested in the minimum cardinality of C that covers P . To start with, let us concentrate on the following problem. Let P be a set of points in \mathbb{R}^{2} in general position and the goal is to figure out the number of simple curves needed to cover P . The solution is trivial – sort the points based on their x -coordinates and join them from left to right; that is we need just one simple curve to cover P . As we move from a simple curve with no restrictions whatsoever, to a straight line, the problem becomes hard and deserves non-trivial solutions [ 18 , 5 , 1 , 20 ] . This obviously gives rise to a natural question about what happens to this problem if we consider point sets with some special configuration, like grids vis-a-vis different kinds of simple curves like circles, convex curves, orthoconvex curves, etc. To bring the variety of different point sets and curves under a unifying framework, we propose the following definition of geometric covering number . Definition 1 . (Geometric covering number) The geometric covering number of a point set P in \mathbb{R}^{d} with respect to a curve type C (like circle, convex curve, orthoconvex curve, etc.), denoted as {\cal G}_{C}(P,d) , is the minimum number of curves of type C needed to cover all the points in P . We say a curve covers a point if the point lies on the curve. If the dimension is implicit, we will just write {\cal G}_{C}(P) instead of {\cal G}_{C}(P,d) . The notion of covering a point set with different geometric structures have been studied in the literature [ 7 , 16 , 9 , 11 , 13 ] . The common theme running through all such problems is about figuring out the minimum number of structures, e.g., trees, paths, line segments, etc., needed to form a cover of the point set. Given a set of points, a covering path is a polygonal path that visits all the points and similarly a covering tree is a tree whose edges are line segments that jointly cover all the points. Covering paths and trees for planar grids have been studied in [ 16 ] , where bounds on the minimum number of line segments of such paths and trees are given. Analogous questions on covering paths and trees for higher dimensional grids have been studied in [ 11 ] . Given a set S of n points in the plane, the problem of finding the smallest number l of straight lines needed to cover all n points in S have been studied in [ 13 ] , where bounds on the time complexity of this problem in terms of n and l (assuming l to be small) is given. In [ 9 ] , the notion of geometric thickness of complete graphs is studied, where geometric thickness of a graph is defined to be the smallest number of layers such that we can draw the graph in the plane with straight-line edges and assign each edge to a layer so that no two edges on the same layer cross. The intersection of a convex body with a lattice is called a convex set of lattice points . Several problems, conjectures and results on covering a convex set of lattice points by minimum number of lines, hyperplanes, or other subspaces have been discussed in [ 7 ] . On the other hand, incidence problems in geometry [ 21 , 22 ] studies questions about finding the maximum possible number of pairs (p,\ell) such that p is a point belonging to a set of points and \ell is a line belonging to a set of lines and p lies on \ell . Incidence between points and other geometric structures like circles, planes, algebraic curves, etc. have also been studied. We do not intend to go into all of them as an interested reader can find them in [ 21 , 22 ] . On the other hand, researchers have studied the problems of point line cover , or its more general form of point curve cover [ 18 , 5 , 1 , 20 ] . These problems consist of a set P of n points on the plane and a positive integer k , and the question is whether there exists a set of at most k lines/hyperplanes/curves which cover all points in P . They are computationally hard problems, motivated from set cover , and the effort has been mostly in parametrized complexity where researchers focussed on finding tight kernels [ 8 ] for the problems [ 18 , 5 , 1 , 20 ] . Notations: [x] will denote the set of natural numbers \{1,2,\ldots,x\} . P will denote a set of n points in dimension \mathbb{R}^{d} . Unless otherwise stated, P will be finite. Organization of the paper: In this paper, we study the notion of geometric covering number for a few types of curves. For most of the cases, our point set is a grid that we want to cover with a particular kind of curve. For completeness sake, we start with lines, the simplest curve, covering a finite grid in Section 2 . We also investigate a converse question of covering in Section 2.2 . Very simply put, the converse question deals with the following notion – if there is a guarantee that some lines cover an “unknown” point set, then can we say something about the configuration of the point set? From lines, we move onto monotone curves in Section 3 . Section 4 considers three types of closed curves – circles, convex curves, orthoconvex curves. Section 5 brings into focus covering with non-congruent curves. In Section 6 , we study covering by some small curves. Finally, Section 7 sums up the findings in this work. We feel our work will motivate studying the geometric covering number for more point set and curve pairs. 2 Covering by lines and its converse problem In the first part of this section, we consider covering grids by

Read the complete text