Intersections and unions

The collection of convex subsets of a vector space has the following properties:

Figure: Intersection of Convex sets $A$ and $B$, (a) 2-dimensional, (b) 2-dimensional, (c) 3-dimensional, are all convex.

1.

The empty set and the whole vector-space are convex.

2.

The intersection of any collection of convex sets is convex(figure ).

3.

The union of a non-decreasing sequence of convex subsets is a convex set. For the preceding property of unions of non-decreasing sequences of convex sets, the restriction to nested sets is important: The union of two convex sets need not be convex.

For example, the non-decreasing convex sets are $C_1 = \{a, b\}$, and $C_2 = \{a, b, c\}$. Then, their union, $C_1 \cup C_2 = \{a, b, c\}$, is obviously, a convex set.

Definition 3.5   Jordan curve theorem. In topology, a Jordan curve is a non-self-intersecting continuous loop in the plane. The Jordan curve theorem asserts that every Jordan curve divides the plane into an “interior” region bounded by the curve and an “exterior” region containing all of the nearby and far away exterior points, so that any continuous path connecting a point of one region to a point of the other region intersects with that loop somewhere.

Hence, any two points $p, q$ outside a Jordan curve will intersect even number of times, and two pointer $p, r$, one is outside and other inside will intersect the curve odd number of times (see figure (a), and (b)).

Figure: Jordan Curve.

Consider the following problem. Given a simple closed Jordan polygon curve, determine if the interior region enclosed by the curve is convex. This problem can be readily solved solved by observing that if line segment defined by all pairs of vertices of the polygon curve, $\overline{v_i, v_j}, i \neq j, 1 \leq i, j \leq n$, where $n$ denotes the total number of vertices, lie totally inside the region, then the region is convex.

This would yield a straight algorithm with time complexity $O(n^3)$, as there are $O(n^2)$ line segments, and to test if each line segment lies totally in the region takes $O(n)$ time by comparing it against every polynomial segment.

It may be noted that the interior angle of each vertex must be strictly less than $\pi$, in order for the region to be convex. If it is more than $\pi$ it is reflex. It may be noted that all the vertices must be convex, is the necessar condition for the region to be convex.