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

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.

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.