3
$\begingroup$

I have several connected questions. In short form, I want to set N points on plane by intersecting as few lines/circles/conics as possible.

  1. Given $N$ points on 2D plane, how many straight lines and/or conics are needed to get all these points as intersections?

  2. The same as (1) but there should be no other intersections; that is, exactly $N$ intersections. Possible additional constraints for special cases:

    • only straight lines allowed;
    • only circles allowed;
    • only conics are allowed;
    • there are no three collinear points;
    • there are no four concircular points;
    • there are no six points that are on the same conic (BTW, is this true that any five points on plane will determine a conic?);
    • maybe something else?

Thanks for any help!

  • 0
    @stannic: Yes, thanks; I meant the straight-line version of (2).2011-09-18

2 Answers 2

1

In the straight line case, in general each line will pass through at most two points if no three are collinear, and each point needs at least two lines, so you need as many lines as points (the fraction mentioned below is $\frac{2}{2}$) if there are at least three points. If there are two points, you need three lines, if one point then two lines.

Typically if there are more than three points and no three are collinear then there will be extra intersections.

For conic sections you get something similar: each conic section will pass through up to five points and each point needs two conic sections, so the number of conic sections must be at least $\frac{2}{5}$ of the number of points (rounded up), with two conic sections needed if you have one or two points, and three needed if you have five points. For circles the pattern is similar, with the fraction becoming $\frac{2}{3}$, with two circles needed for one point and three circles need for three points; with circles you can avoid extra intersections for example by using extra circles which touch tangentially rather than intersecting twice.

2

There are too many cases here, so I'll just look at one of the most basic: question (1) with $N$ points in general position, conics, and no additional constraints. So any 5 of the points will determine a conic, which misses all the other points (since they are in general position). On the other hand, each point must be in at least two conics. Thus if there are $N$ points and $C$ conics, the number of (conic,point) pairs is at most $5C$ and at least $2N$. The smallest possible number of conics is $\lceil 2N/5 \rceil$. However, this doesn't take into account the fact that no two distinct conics can intersect the same 5 points. Thus for $N=5$ you need 3 conics rather than 2. I don't think this is a problem for any $N > 5$.