Convexity algorithms in parallel coordinates

Publisher Website
Google Scholar
Abstract
With a system of parallel coordinates , objects in R N can be represented with planar “ graphs ” (i.e., planar diagrams) for arbitrary N [21]. 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 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, are derived. By virtue of the duality, these algorithms also apply to polygons whose edges are a certain class of convex curves. These planar constructions are studied prior to exploring generalizations to N -dimensions. The needed results on parallel coordinates are given first.

This publication has 16 references indexed in Scilit: