Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
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. –  J. M. Sep 18 '11 at 17:39
    
@J.M.: Yes, probably I get it. There is some info on (mathworld.wolfram.com/ConicSection.html), I have not read yet. –  stannic Sep 18 '11 at 17:59
    
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. –  Robert Israel Sep 18 '11 at 17:59
    
@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. –  stannic Sep 18 '11 at 18:07
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. –  Joseph O'Rourke Sep 18 '11 at 18:11

2 Answers 2

up vote 0 down vote accepted

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.

share|improve this answer
    
Thanks, I'll investigate it. I accepted your answer. –  stannic Sep 18 '11 at 18:59

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$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.