### Convexity algorithms in parallel coordinatesConvexity algorithms in parallel coordinates

Access Restriction
Subscribed

 Author Inselberg, Alfred ♦ Reif, Mordechai ♦ Chomut, Tuval Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©1987 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Abstract With a system of parallel coordinates, objects in $\textit{RN}$ can be represented with planar $“\textit{graphs}”$ (i.e., planar diagrams) for arbitrary $\textit{N}$ [21]. In $\textit{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 $\textit{O}(\textit{n})$ time and the convex hull on the plane in $\textit{O}(log$ $\textit{n})$ for real-time and $\textit{O}(\textit{n}$ log $\textit{n})$ worst-case construction, where $\textit{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 $\textit{N}-dimensions.$ The needed results on parallel coordinates are given first. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 1987-10-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 34 Issue Number 4 Page Count 37 Starting Page 765 Ending Page 801

#### Open content in new tab

Source: ACM Digital Library