article

Free access

Convexity algorithms in parallel coordinates

Authors:

Alfred Inselberg,

Mordechai Reif,

Tuval ChomutAuthors Info & Claims

Journal of the ACM (JACM), Volume 34, Issue 4

Pages 765 - 801

https://doi.org/10.1145/31846.32221

Published: 01 October 1987 Publication History

PDF eReader

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², 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]

AHO, A. V., HO~ROFT, J. E., AND ULLMAN, J. D. The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, Mass., 1974, pp. 152-161.

Crossref

Google Scholar

[2]

ANDREWS, D.F. Plots of high-dimensional data. Biometrics 29 (1972), 125-136.

Google Scholar

[3]

ASIMOV, D. The grand tour: A tool for viewing multidimensional data. SIAM J. Sci. Stat. Comput. 6 (1985), 128-143.

Crossref

Google Scholar

[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.

Google Scholar

[5]

BARNETT, V., ED. Interpreting Multivariate Data. Wiley, New York, 1981.

Google Scholar

[6]

BENTLEY, j. L., AND SHAMOS, M. I. Divide and conquer for linear expected time. Inf. Proc. Lett. 7 (1978), 87-97.

Google Scholar

[7]

BOLTYANSKII, V.G. Envelopes, Translated from the Russian by R. B. Brown. Pergamon Press, New York, 1964.

Google Scholar

[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.

Google Scholar

[9]

BRODETSKY, O. S. A First Course in Nomography. G. Bell & Sons, London, England (first published 1920), 1949.

Google Scholar

[10]

BURTON, R. P., AND SMITH, D.R. A hidden-line algorithm for hyperspace. SIAM J. Comput. 11 (1982), 71-80.

Google Scholar

[11]

COHAN, S. Mobility Analysis using Parallel Coordinates. Mech. Mach. Theory 21 (1986), 63-71.

Google Scholar

[12]

COXETER, H. S.M. Projective Geometry. University of Toronto Press, Toronto, Ont., Canada, 1974.

Google Scholar

[13]

DEVROYE, L., AND TOUSSAINT, G.T. A note on linear expected time algorithms for finding convex hulls. Computing 26 ( 198 I), 361-366.

Google Scholar

[14]

DIMSDALE, B. Conic Transformations. Rep. G320-2713. IBM Los Angeles Scientific Center, Los Angeles, Calif., 198 I.

Google Scholar

[15]

DIMSDALE, B. Conic Transformations & Projectivities. Rep. G320-2753. IBM Los Angeles Scientific Center, LOs Angeles, Calif., 1984.

Google Scholar

[16]

EDELSBRUNNER, H., AND VAN LEEUWEN, K. Multi-Dimensional Structures and Algorithms, a Bibliography. IIG, Rep. 104, Technische Univ., Graz, Austria, 1983.

Google Scholar

[17]

FENCHEL, W. Convex cones, sets and functions. Princeton Univ., Princeton, N.J., 1951.

Google Scholar

[18]

FRIEDMAN, J., AND TUKEY, J. A projection pursuit algorithm for exploratory data analysis. IEEE Trans. Comput. C-23 (1974), 881-890.

Google Scholar

[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.

Google Scholar

[20]

HILBERT, n., AND COHN-VOSSEN, n.S. Geometry and the Imagination. Chelsea, New York, 1952.

Google Scholar

[21]

INSELBERG, A. N-dimensional graphics. Part I: Lines & hyperplanes. Pep. G320-2711. IBM Los Angeles Scientific Center, LOs Angeles, Calif., 1981.

Google Scholar

[22]

INSELBERG, A. The plane with parallel coordinates (special issue on computational geometry). Visual Comput. 1 (1985), 69-91.

Google Scholar

[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.

Google Scholar

[24]

INSELBERG, A., AND DIMSDALE, B. Representing Multi-Dimensional Lines. Submitted for publication.

Google Scholar

[25]

KLEE, V.L. Asymptotes and projections of convex bodies. Math. Scand. 8 (1960), 356-362.

Google Scholar

[26]

gLEE, V.L. Asymptotes of convex bodies. Math. Scand. 20 (1967), 89-90.

Google Scholar

[27]

LEE, D. T., AND PREPARATA, F.P. Computational geometry--A survey. IEEE Trans. Comput. C-33 (1984), 1072-1101.

Google Scholar

[28]

MANSOURI, N., AND TOUSSAINT, G. A linear algorithm for reachability region of a ladder between 2 convex polygons. In preparation.

Google Scholar

[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.

Google Scholar

[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.

Google Scholar

[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.

Google Scholar

[32]

ROCKAFELLAR, R.T. Convex Analysis. Princeton University Press, Princeton, N.J., 1970.

Google Scholar

[33]

SCHAFFER, A. A., AND VAN WYCK, C. J. Convex hulls of piecewise smooth Jordan curves. J. Algorithm 8 (1987), 66-94.

Crossref

Google Scholar

[34]

TOUSSAINT, G.T. A simple linear algorithm for intersecting convex polygons (special issue on computational geometry). Visual Comput. 1 (1985), 118-123.

Google Scholar

[35]

WEGMAN, E. Hyperdimensional data analysis using parallel coordinates. Tech. Rep. 1. Center for Computer Statistics and Probability, George Mason Univ., 1986. Submitted for publication.

Google Scholar

Cited By

View all

Gonzalez JDang T(2021)OutViz: Visualizing the Outliers of Multivariate Time SeriesProceedings of the 12th International Conference on Advances in Information Technology10.1145/3468784.3471606(1-5)Online publication date: 29-Jun-2021
https://dl.acm.org/doi/10.1145/3468784.3471606
Gajjar SKulahci MPalazoglu A(2020)Least Squares Sparse Principal Component Analysis and Parallel Coordinates for Real-Time Process MonitoringIndustrial & Engineering Chemistry Research10.1021/acs.iecr.0c0174959:35(15656-15670)Online publication date: 9-Aug-2020
https://doi.org/10.1021/acs.iecr.0c01749
Wang BZhang TChang ZRistaniemi TLiu G(2017)3D Matrix-Based Visualization System of Association Rules2017 IEEE International Conference on Computer and Information Technology (CIT)10.1109/CIT.2017.39(357-362)Online publication date: Aug-2017
https://doi.org/10.1109/CIT.2017.39
Show More Cited By

Index Terms

Convexity algorithms in parallel coordinates
1. Theory of computation
  1. Models of computation
    1. Concurrency
      1. Parallel computing models
  2. Randomness, geometry and discrete structures
    1. Computational geometry

Recommendations

Parallel coordinates: a tool for visualizing multi-dimensional geometry
VIS '90: Proceedings of the 1st conference on Visualization '90

A methodology for visualizing analytic and synthetic geometry in R^N is presented. It is based on a system of parallel coordinates which induces a non-projective mapping between N-Dimensional and 2-Dimensional sets. Hypersurfaces are represented by their ...
Terracini convexity
Abstract
We present a generalization of the notion of neighborliness to non-polyhedral convex cones. Although a definition of neighborliness is available in the non-polyhedral case in the literature, it is fairly restrictive as it requires all the low-...
Efficient Algorithms to Test Digital Convexity
Discrete Geometry for Computer Imagery
Abstract
A set is digital convex if , where denotes the convex hull of S. In this paper, we consider the algorithmic problem of testing whether a given set S of n lattice points is digital convex. Although convex hull computation requires time even for ...

Reviews

Reviewer: Thomas Rainer Michael Fischer

This paper describes a methodology for representing multidimensional objects in a system of parallel coordinates, which allows users to visualize such objects by using planar diagrams. It begins with a thorough discussion of the implications of a point-line duality induced by parallel coordinates. From these results the authors derive algorithms for constructing the intersection and convex merge of convex polygons in O( n) time and for constructing the convex hull on the plane in O(log n) time (real-time) and O( n log n) time (worst-case). These algorithms also imply generalizations for polygons whose edges are convex curves. The main purpose was to study the planar case for extracting some guidelines for deriving multidimensional equivalents of these algorithms. The paper is carefully written and self-contained. More than 40 figures help the reader get the necessary intuition on working with parallel coordinates. Due to the restriction to planar instances, however, the advantages of this approach over existing algorithms are not apparent.

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Journal of the ACM Volume 34, Issue 4

Oct. 1987

254 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/31846

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 October 1987

Published in JACM Volume 34, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

55
Total Citations
View Citations
938
Total Downloads

Downloads (Last 12 months)49
Downloads (Last 6 weeks)6

Reflects downloads up to 09 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Gonzalez JDang T(2021)OutViz: Visualizing the Outliers of Multivariate Time SeriesProceedings of the 12th International Conference on Advances in Information Technology10.1145/3468784.3471606(1-5)Online publication date: 29-Jun-2021
https://dl.acm.org/doi/10.1145/3468784.3471606
Gajjar SKulahci MPalazoglu A(2020)Least Squares Sparse Principal Component Analysis and Parallel Coordinates for Real-Time Process MonitoringIndustrial & Engineering Chemistry Research10.1021/acs.iecr.0c0174959:35(15656-15670)Online publication date: 9-Aug-2020
https://doi.org/10.1021/acs.iecr.0c01749
Wang BZhang TChang ZRistaniemi TLiu G(2017)3D Matrix-Based Visualization System of Association Rules2017 IEEE International Conference on Computer and Information Technology (CIT)10.1109/CIT.2017.39(357-362)Online publication date: Aug-2017
https://doi.org/10.1109/CIT.2017.39
Gajjar SPalazoglu A(2016)A data-driven multidimensional visualization technique for process fault detection and diagnosisChemometrics and Intelligent Laboratory Systems10.1016/j.chemolab.2016.03.027154(122-136)Online publication date: May-2016
https://doi.org/10.1016/j.chemolab.2016.03.027
Liu JLi JOksel CMa CWang X(2016)Visualization of Multidimensional Data for Nanomaterial CharacterizationNanomaterial Characterization10.1002/9781118753460.ch13(269-286)Online publication date: 22-Apr-2016
https://doi.org/10.1002/9781118753460.ch13
Di HTang XWang S(2015)A novel high-dimension data visualization method based on concept color spectrum diagram2015 IEEE 11th International Colloquium on Signal Processing & Its Applications (CSPA)10.1109/CSPA.2015.7225634(140-144)Online publication date: Mar-2015
https://doi.org/10.1109/CSPA.2015.7225634
Hayashi AItoh TNakamura S(2014)A Visual Analytics Tool for System Logs Adopting Variable Recommendation and Feature-Based Filtering属性推薦と特徴ベースフィルタリングを用いたシステムログ分析のための可視化手法The Journal of the Society for Art and Science10.3756/artsci.13.18513:3(185-197)Online publication date: 15-Sep-2014
https://doi.org/10.3756/artsci.13.185
Sawitzki G(2014)ReferencesComputational Statistics10.1201/b17179-7(233-235)Online publication date: 23-Jul-2014
https://doi.org/10.1201/b17179-7
Inselberg A(2014)A Visual Excursion into Parallel Coordinates (Extended Abstract)Man-Machine Interactions 310.1007/978-3-319-02309-0_4(43-52)Online publication date: 2014
https://doi.org/10.1007/978-3-319-02309-0_4
Andrienko GAndrienko N(2013)Blending Aggregation and Selection: Adapting Parallel Coordinates for the Visualization of Large DatasetsThe Cartographic Journal10.1179/000870405X5728442:1(49-60)Online publication date: 18-Jul-2013
https://doi.org/10.1179/000870405X57284
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Index Terms

Recommendations

Parallel coordinates: a tool for visualizing multi-dimensional geometry

Terracini convexity

Efficient Algorithms to Test Digital Convexity

Reviews

Access critical reviews of Computing literature here

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations