Narrow Results

We show that finding the simplices containing a fixed given point among those defined on a set of n points can be done in O(n + k) time for the two-dimensional case, and in O(n² + k) time for the three-dimensional case, where k is the number of these simplices.

As a byproduct, we give an alternative (to the algorithm in Ref. 4) O(n log r) algorithm that finds the red-blue boundary for n bichromatic points on the line, where r is the size of this boundary. Another byproduct is an O(n² + t) algorithm that finds the intersections of line segments having two red endpoints with those having two blue endpoints defined on a set of n bichromatic points in the plane, where t is the number of these intersections.

There are three constructions of which I know that yield higher dimensional analogues of Sierpinski’s triangle. The most obvious is to remove the open convex hull of the midpoints of the edges of the $n$-simplex. The complement is a union of simplices. Continue the removal recursively in each of the remaining sub-simplices. The result is an uncountably infinite figure in $n$-dimensional space that is Cantor-like in a manner analogous to the Sierpinski triangle. A countable analogue is obtained by means of playing the chaos game in the $n$-simplex. In this “game” one chooses a random $(n+1)$-ary sequence; starting from the initial point (that is identified with a vertex of the simplex), one continues to plot points by moving half-again as much towards the next point in the sequence. The resulting plot converges to the figure described above. Similarly, coloring the multinomial coefficients black or white according to their parity results in a similar figure, when the $n$-dimensional analogue of the Pascal triangle is rescaled and embedded in space.