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!

  • 1
    The term of art is *concyclic*, not "concircular". As for "five points determine a conic", note that the general equation for a conic has six parameters, one of which you can fix. That leaves five or so free parameters... ;) Additionally: four points determine a unique parabola passing through them.2011-09-18
  • 0
    @J.M.: Yes, probably I get it. There is some info on (http://mathworld.wolfram.com/ConicSection.html), I have not read yet.2011-09-18
  • 0
    It's not quite true that _any_ five points determine a conic. Degenerate cases mess this up. Consider five collinear points, or four collinear and one other.2011-09-18
  • 0
    @Robert Israel: Yes. Also, if points do not form a convex hull then the conic cannot be ellipse. Probably this leads to many special cases.2011-09-18
  • 1
    I don't think (2) can always be solved: consider three points at the vertices of a triangle and one point interior to the triangle. For the straight-line version of (1), I suspect it is NP-hard, because it is NP-hard to *cover* a set of points with a minimum number of lines. See, e.g., "Covering Points with Lines," by Stefan Langerman and Pat Morin.2011-09-18
  • 0
    @Joseph O'Rourke: Given triangle ABC and interior point D, one can draw hyperbola through ADC, so that other branch goes through B; other hyperbola goes through BDC, and other branch goes through A. So we have intersections A, B, C, D. From (http://mathworld.wolfram.com/ConicSection.html): Two conics that do not coincide or have an entire straight line in common cannot meet at more than four points (Hilbert and Cohn-Vossen 1999, pp. 24 and 160).2011-09-18
  • 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$.