1
$\begingroup$

I'm looking for a proof for this question/near-answer

Take any set of $K$ points on the plane where no $3$ are colinear. How many line segments can be created, regardless of order, before any intersect?

Create a convex polygon using the points as vertices, such that it encompasses all other points, it will be an $N$-gon. Then with the remaining interior points do the same, until you have no points, the last polygon(sometimes a line or point) will have $V$ vertices.

The number will be based on $K,N,\&V$ and will roughly be $3N-K$

$\endgroup$
1
$\begingroup$

Your tag choice was right. :-) Any maximal configuration of non-intersecting segments between given points can be considered as a plane graph $G$, whose outer face is the $N$-gon. Count the number $x$ of pairs $(e,f)$ where $e$ is an edge incident to a face $f$ of the graph $G$. Since each but outer face of $G$ has at least $3$ egdes and the outer face of $G$ has $N$ edges, $x\ge 3(f(G)-1)+N$, where $f(G)$ denotes the number of faces of $G$. On the other hand, each edge of the graph $G$ is incident to at most two faces of $G$, so $x\le 2e(G)$, where $e(G)$ denotes the number of edges of $G$. Thus $2e(G)\ge 3f(G)+N-3$. By Euler’s formula, $f(G)=e(G)-K+2$. It follows $e(G)\le 3K-N-3$. This upper bound is achieved by any almost-triangulation $G$, that is when $G$ has all but the outer faces triangles. We can construct one of them recursively as follows. Pick any vertex $v$ of the $N$-gon, construct an almost triangulation $G’$ on the remaining points, an then connect by segments the vertex $v$ with the vertices of the outer face of $G’$ which are visible from $v$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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