Access Restriction

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

   Open content in new tab
Source: ACM Digital Library