CONVEXITY ALGORITHMS IN PARALLEL COORDINATES

With a system of parallel coordinates, objects in R**N can be represented with planar 'graphs' (ie. , planar diagrams) for arbitrary N. In R**2, embedded in the projective plane, parallel coordinates induce a point-line duality. This yields a new duality between bounded and unbounded convex sets and hstars (a generalization of hyperbolas), as well as a duality between convex union (convex merge) and intersection. From these results, algorithms are derived for constructing the intersection and convex merge of convex polygons in O(n) time and the convex hull on the plane in O(log n) for real-time and O(n log n) worst-case construction, where n is the total number of points. By virtue of the duality, these algorithms also apply to polygons whose edges are a certain class of convex curves.