Convexity algorithms in parallel coordinates

ABSTRACT

With a system of parallel coordinates, objects in RN can be represented with planar “graphs” (i.e., planar diagrams) for arbitrary N [21]. In R2, 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.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: ANDREWS, D.F. Plots of high-dimensional data. Biometrics 29 (1972), 125-136.
• 3: Daniel Asimov, The grand tour: a tool for viewing multidimensional data, SIAM Journal on Scientific and Statistical Computing, v.6 n.1, p.128-143, Jan. 1985 [doi>10.1137/0906011]
• 4: BANCHOFF, T. F., AND STRAUSS, C.M. Real time computer graphics analysis of figures in fourspace. In Hypergraphics: Visualizing Complex Relationships in Art, Science and Technology, D. Brissom, Ed. American Association for the Advancement of Science, Westview Press, Boulder, Colo., 1979, pp. 159-167.
• 5: BARNETT, V., ED. Interpreting Multivariate Data. Wiley, New York, 1981.
• 6: BENTLEY, j. L., AND SHAMOS,, M. I. Divide and conquer for linear expected time. Inf. Proc. Lett. 7 (1978), 87-97.
• 7: BOLTYANSKII, V.G. Envelopes, Translated from the Russian by R. B. Brown. Pergamon Press, New York, 1964.
• 8: BmssOM, D., ED. Hypergraphics: Visualizing Complex Relationships in Art, Science and Technology. American Association for the Advances of Science, Westview Press, Boulder, Colo., 1979.
• 9: BRODETSKY, O. S. A First Course in Nomography. G. Bell & Sons, London, England (first published 1920), 1949.
• 10: BURTON, R. P., AND SMITH, D.R. A hidden-line algorithm for hyperspace. SIAM J. Comput. 11 (1982), 71-80.
• 11: COHAN, S. Mobility Analysis using Parallel Coordinates. Mech. Mach. Theory 21 (1986), 63-71.
• 12: COXETER, H. S.M. Projective Geometry. University of Toronto Press, Toronto, Ont., Canada, 1974.
• 13: DEVROYE, L., AND TOUSSAINT, G.T. A note on linear expected time algorithms for finding convex hulls. Computing 26 ( 198 I), 361-366.
• 14: DIMSDALE, B. Conic Transformations. Rep. G320-2713. IBM Los Angeles Scientific Center, Los Angeles, Calif., 198 I.
• 15: DIMSDALE, B. Conic Transformations & Projectivities. Rep. G320-2753. IBM Los Angeles Scientific Center, LOs Angeles, Calif., 1984.
• 16: EDELSBRUNNER, H., AND VAN LEEUWEN, K. Multi-Dimensional Structures and Algorithms, a Bibliography. IIG, Rep. 104, Technische Univ., Graz, Austria, 1983.
• 17: FENCHEL, W. Convex cones, sets and functions. Princeton Univ., Princeton, N.J., 1951.
• 18: FRIEDMAN, J., AND TUKEY, J. A projection pursuit algorithm for exploratory data analysis. IEEE Trans. Comput. C-23 (1974), 881-890.
• 19: GUmAS, L., RAMSHAW, L., AND STOLFI, J. A kinetic framework for computational geometry. In Proceedings of the IEEE Annual Symposium on Foundations of Computer Science. IEEE, New York, 1983, pp. 100-111.
• 20: HILBERT, n., AND COHN-VOSSEN, n.S. Geometry and the Imagination. Chelsea, New York, 1952.
• 21: INSELBERG, A. N-dimensional graphics. Part I: Lines & hyperplanes. Pep. G320-2711. IBM Los Angeles Scientific Center, LOs Angeles, Calif., 1981.
• 22: INSELBERG, A. The plane with parallel coordinates (special issue on computational geometry). Visual Comput. 1 (1985), 69-91.
• 23: INSELBERG, A. Intelligent instrumentation and process control. In Proceedings of the 2nd Conference on Artificial Intelligence. IEEE Computer Society Press, Washington, D.C., 1985, pp. 302-307.
• 24: INSELBERG, A., AND DIMSDALE, B. Representing Multi-Dimensional Lines. Submitted for publication.
• 25: KLEE, V.L. Asymptotes and projections of convex bodies. Math. Scand. 8 (1960), 356-362.
• 26: gLEE, V.L. Asymptotes of convex bodies. Math. Scand. 20 (1967), 89-90.
• 27: LEE, D. T., AND PREPARATA, F.P. Computational geometry--A survey. IEEE Trans. Comput. C-33 (1984), 1072-1101.
• 28: MANSOURI, N., AND TOUSSAINT, G. A linear algorithm for reachability region of a ladder between 2 convex polygons. In preparation.
• 29: O'ROURKE, J., CHIEN, C.-B., OLSON, T., AND NADDOR, D. A new linear algorithm for intersecting convex polygons. Comput. Graph. Image Process. 19 (1982), 384-391.
• 30: PREPARATA, F. P., AND MULLER, D.E. Finding the intersection of a set of N half-spaces in time O(N log N). Theoret. Comput. Sci. 8 (1979), 45-55.
• 31: RIVERO, J., AND INSELBERG, A. Extension al analisis del espacio de fase de systemas dinamicos pot las coordenadas paralelas. Rep. G320-2742. IBM Los Angeles Scientific Center, Los Angeles, Calif., 1984.
• 32: ROCKAFELLAR, R.T. Convex Analysis. Princeton University Press, Princeton, N.J., 1970.
• 32a: Alejandro A. Schäffer , Christopher J. Van Wyk, Convex hulls of piecewise-smooth Jordan curves, Journal of Algorithms, v.8 n.1, p.66-94, March 1987 [doi>10.1016/0196-6774(87)90028-9]
• 33: TOUSSAINT, G.T. A simple linear algorithm for intersecting convex polygons (special issue on computational geometry). Visual Comput. 1 (1985), 118-123.
• 34: WEGMAN, E. Hyperdimensional data analysis using parallel coordinates. Tech. Rep. 1. Center for Computer Statistics and Probability, George Mason Univ., 1986. Submitted for publication.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

General Terms:
Algorithms, Performance, Theory, Verification