“Reliable two-dimensional graphing methods for mathematical formulae with two free variables” by Tupper

  • ©Jeff Tupper

Conference:


Type:


Title:

    Reliable two-dimensional graphing methods for mathematical formulae with two free variables

Presenter(s)/Author(s):



Abstract:


    This paper presents a series of new algorithms for reliably graphing two-dimensional implicit equations and inequalities. A clear standard for interpreting the graphs generated by two-dimensional graphing software is introduced and used to evaluate the presented algorithms. The first approach presented uses a standard interval arithmetic library. This approach is shown to be faulty; an analysis of the failure reveals a limitation of standard interval arithmetic. Subsequent algorithms are developed in parallel with improvements and extensions to the interval arithmetic used by the graphing algorithms. Graphs exhibiting a variety of mathematical and artistic phenomena are shown to be graphed correctly by the presented algorithms. A brief comparison of the final algorithm presented to other graphing algorithms is included.

References:


    1. Ron Avitzur,Olaf Bachmann, and Norbert Kajler. From Honest to Intelligent Plotting.In A.H.M.Levelt,editor, Proc.of the International Symp.on Symbolic and Algebraic Computat on (ISSAC ’95),Montreal,Canada , pages 32 – 41.ACM Press,1995.
    2. Dennis S.Arnon.Topologically Reliable Display of Algebraic Curves.Computer Graphics (SIGGRAPH 83 Conference Proceed ngs),17(3):219 – 227,July 1983.
    3. J.Comba and J.Stolfi Affine Arithmetic an its Applications to Computer Graphics.In Anais do VI Symposio Bras le ro de Computa, computacao Grafia e Processamento de Imagens (SIBGRAPI ’93),pages 9 – 18,1993.
    4. Jack J.Dongarra. Performance of Various Computers Using Standar Linear Equations Software. Technical Report CS-89-85,University of Tennessee, 2000.
    5. Jack Dongarra, Ree Wade, and Paul McMahan. Linpack Benchmark – Java Version. http ://www.netlib.org /benchmark/linpackjava, 2000.
    6. R.Fateman. Honest Plotting, Global Extrema an Interval Arithmetic.In P.S.Wang, editor, Proc. of the International Symp. on Symbolic and Algebra c Computat on (ISSAC ’92), Berkeley, USA , pages 216 – 223. ACM Press, 1992.
    7. Eldon Hansen. Global Optimization Using Interval Analysis – The Multi-Dimensional Case. Numerische Mathematik ,34(3):247 – 270, 1980.
    8. Timothy J. Hickey, Zhe Qiu, and Maarten H. van Emden. Interval Constraint Plotting for Interactive Visual Exploration of Implicitly Defined Relations. Reliable Computing ,6(1):81 – 92, 2000.
    9. IEEE Task P754.ANSI/IEEE 754-1985, Standard for Binary Floating-Point Arithmetic .IEEE, New York, NY, USA, August 1985. Revise 1990. A preliminary draft was published in the January 1980 issue of IEEE Computer,together with several companion articles.Also stan ardize as IEC 60559 (1989-01)B nary .oating-po nt arithmetic for microprocessor systems .
    10. W.M.Kahan.A More Complete Interval Arithmetic.Lecture notes prepare for a summer course at the University of Michigan,June 17 – 21,1968.
    11. Metrowerks.Macintosh Linpack Benchmark. http://www.metrowerks.com/benchmarks/desktop/ mac_linpack.html , 1999.
    12. Tom Michiels.http://www.cs.kuleuven.ac.be/~tomm/ bench.html , 2000. 13. R.E.Moore.Interval Analysis . Prentice Hall, dEnglewood Cliffs, New Jersey, 1966.
    14. R.E.Moore. Methods and Applications of Interval Analysis. SIAM, Philadelphia, 1979.
    15. Pedagoguery Software Inc.GrafEq TM . http://www.peda.com/grafeq .
    16. H. Ratschek an J. Rokne. New Computer Methods for Global Optimization .Ellis Horwoo Ltd.,Chichester, 1988.
    17. John M. Snyder.Generative Modeling for Computer Graphics and CAD:Symbol c Shape Des gn Us ng Interval Analysis .Aca emic Press,San Diego,1992.
    18. John M. Snyder. Interval Analysis for Computer Graphics. Computer Graphics (SIGGRAPH 92 Conference Proceedings), 26(2):121 – 130, July 1992.
    19. Gabriel Taubin. An Accurate Algorithm for Rasterizing Algebraic Curves.In Second Symposium on Solid Modeling . ACM SIGGRAPH and IEEE Computer Society,May 1993.
    20. Gabriel Taubin.Distance Approximations for Rasterizing Implicit Curves.ACM Transactions on Graphics , 13(1):3 – 42,January 1994.
    21. Jeffrey Allen Tupper.Graphing Equations with Generalize Interval Arithmetic.Master ‘s thesis,University of Toronto,1996.


ACM Digital Library Publication: