The design of LINETOOL, a geometric editor

ABSTRACT

We describe the design of LINETOOL, a geometric editor. Researchers in the areas of computational geometry, robotics and algebraic computation need a graphical editor for composing geometric objects which does more than simply turn pixels on and off on the screen. This system will be a tool to help researchers make and demolish conjectures, and to experiment with ideas. Our editor will allow users to define geometric scenes by declaring geometric objects built up from constants, dependent and independent variables, and geometric constraints. The system will solve for the constraints, and display the resulting scene. The user may then make queries about spatial relationships between components of geometric objects in the scene, which will be answered correctly, that is, without errors due to numerical approximations.

REFERENCES

• 1: Adobe Systems Incorporated. POSTSCRIPT Language Tutorial and Cookbook. Addison-Wesley, 1985.
• 2: Varol Akman. Geometry and graphics applied to robotics. In {18}, pages 619-638.
• 3: Dennis S. Arnon, Geometric reasoning with logic and algebra, Artificial Intelligence, v.37 n.1-3, p.37-60, Dec. 1988 [doi>10.1016/0004-3702(88)90049-5]
• 4: Alan Hamilton Borning, Thinglab--a constraint-oriented simulation laboratory., 1979
• 5: Adrian Bowyer, James Davenport, Philip Milne, Julian Padget and Andrew Wallis. A geometric algebra system. Draft, December 1987, Schools of Mechanical Engineering and Mathematical Sciences, University of Bath, Bath, Avon BA2 7AY, UK.
• 6: D. Brownawell. Bounds for the degrees in the Nullstellensatz. Annals of Math. Second Series, 126 (3) 1987, pages 577-591.
• 7: Bruno Buchberger. GrSbner bases: An algorithmic method in polynomial ideal theory. In N.K. Bose, editor, Multidimensional Systems Theory, pages 184-232. D. Reidel, 1985.
• 8: Bruno Buchberger. What can GrSbner bases do for computational geometry and robotics? In {23}.
• 9: B. Buchberger , George E. Collins , Rudiger Loos , Rudolf Albrecht, Computer algebra: symbolic and algebraic computation (2nd ed.), Springer-Verlag New York, Inc., New York, NY, 1983
• 10: Bruno Buchberger and R. Loos. Algebraic simplification. In {9}, pages 11-43.
• 11: L. Caniglia, A. Galligo and J. Heintz. Some new effectivity bounds in computational geometry. Preliminary version, 1988. Working Group Noai Fitchas, Instituto Argentino de Mathem~tica, Viamonte 1636, let cuerpo, ler piso, (1055) Buenos Aires, Argentina.
• 12: Shang-Ching Chou. Proving elementary geometry theorems using Wu's algorithm. Contemporary Mathematics 29, pages 243-286. American Mathematical Society, 1984.
• 13: George E. Collins, The Calculation of Multivariate Polynomial Resultants, Journal of the ACM (JACM), v.18 n.4, p.515-532, Oct. 1971 [doi>10.1145/321662.321666]
• 14: George E. Collins, Hauptvortrag: Quantifier elimination for real closed fields by cylindrical algebraic decomposition, Proceedings of the 2nd GI Conference on Automata Theory and Formal Languages, p.134-183, May 20-23, 1975
• 15: Samuel Daniel Conte , Carl W. De Boor, Elementary Numerical Analysis: An Algorithmic Approach, McGraw-Hill Higher Education, 1980
• 16: Thomas Dub& A survey of methods for bounding GrSbner bases. NYU Computer Science Department, February 9, 1987. Courant Institute of Mathematical Sciences, 251 Mercer St., New York, NY 10012.
• 17: Thomas DubS, Bhubaneswar Mishra and Chee-Keng Yap. Admissible orderings and bounds on GrSbner normal form algorithm. NYU Computer Science Department Technical Report 258, Robotics Report 88, Courant Institute of Mathematical Sciences, New York, December, 1986.
• 18: R.A. Earnshaw. Theoretical Foundations of Computer Graphics and CAD. NATO ASI Series Volume F40, Springer-Verlag, Berlin, 1988.
• 19: Lars Warren Ericson. Topologically correct graphical editing in the plane. Robotics Research Technical Report No. 97, Computer Science Division, Courant Institute of Mathematical Sciences, New York University, January, 1987.
• 20: A.R. Forrest. Geometric computing environments: some tentative thoughts, in {18}, pages 185-197.
• 21: Marc Giusti, Some Effectivity Problems in Polynomial Ideal Theory, Proceedings of the International Symposium on Symbolic and Algebraic Computation, p.159-171, July 09-11, 1984
• 22: James Arthur Gosling, Algebraic constraints, 1983
• 23: D. Kapur and J.L. Mundy, editors. Geometric Reasoning, a special issue of ArtificiM Intelligence, contents selected from a Workshop On Geometric Reasoning, Keble College, Oxford University, June 30- July 3, 1986.
• 24: B. Kutzler , S. Stifter, Automated geometry theorem proving using Buchberger's algorithm, Proceedings of the fifth ACM symposium on Symbolic and algebraic computation, p.209-214, July 21-23, 1986, Waterloo, Ontario, Canada [doi>10.1145/32439.32480]
• 25: R. Loos. Computing in algebraic extensions. In {9}, pages 173-187.
• 26: Victor J. Milenkovic, Verifiable implementation of geometric algorithms using finite precision arithmetic, Artificial Intelligence, v.37 n.1-3, p.377-401, Dec. 1988 [doi>10.1016/0004-3702(88)90061-6]
• 27: B. Mishra and C.K. Yap. Notes on GrSbner basis. Technical Report 257, Computer Science Department, New York University, September 1986.
• 28: Ferdinando Mora , H. Michael Möller, The computation of the Hilbert function, Proceedings of the European Computer Algebra Conference on Computer Algebra, p.157-167, March 28-30, 1983
• 29: Greg Nelson, Juno, a constraint-based graphics system, ACM SIGGRAPH Computer Graphics, v.19 n.3, p.235-243, Jul. 1985
• 30: A.C. Norman. Computing in transcendental extensions.
• 31: A. V. Pogorelov. Lectures on the Foundations of Geometry. Noordhoff, 1966.
• 32: Jonathan A. Rees, Norman I. Adams and James R. Meehan. The T Manual. Computer Science Department, Yale University, 1984.
• 33: J. T. Schwartz, Fast Probabilistic Algorithms for Verification of Polynomial Identities, Journal of the ACM (JACM), v.27 n.4, p.701-717, Oct. 1980 [doi>10.1145/322217.322225]
• 34: Jacob T. Schwartz and Micha Sharir. On the "Piano Movers" problem. II. General techniques for computing topological properties of real algebraic manifolds. Advances in Applied Mathematics 4, 298-351. Academic Press, 1983.
• 35: Mark Segal , Carlo H. Séquin, Consistent calculations for solids modeling, Proceedings of the first annual symposium on Computational geometry, p.29-38, June 05-07, 1985, Baltimore, Maryland, United States [doi>10.1145/323233.323238]
• 36: R. V. Southwell. Relaxation Methods in Engineering Science. Oxford University Press, 1940.
• 37: Guy L. Steele, Jr., The Definition and Implementation of a Computer Programming Language Based on Constraints, Massachusetts Institute of Technology, Cambridge, MA, 1980
• 38: Mark Stefik , Daniel Bobrow, Object-oriented programming: Themes and variations, AI Magazine, v.6 n.4, p.40-62, Winter 1986
• 39: Ivan Edward Sutherland. Sketchpad: A Man-Machine Graphical Communication System. PhD Thesis, Massachusetts Institute of Technology, January 1963.
• 40: J.V. Uspensky. Theory of Equations. McGraw-Hill, 1948.
• 41: B.L. van der Waerden. Einfiihrung in die Algebraische Geometrie. Second edition, Springer-Verlag. New York, 1973.
• 42: Christopher John Van Wyk. A Language for Typesetting Graphics. PhD thesis, Stanford University. Also available as Technical Report STAN-CS-80-803, Computer Science Department, Stanford University, June, 1980.
• 43: I.M. Yaglom. A Simple Non-Euclidean Geometry and its Physical Basis. Heidelberg Science Library. Springer- Verlag, 1979.
• 44: Francis Yao and Daniel H. Greene. Finite-resolution computational geometry. 27th Annual Symposium on Foundations of Computer Science, October 27-29, 1986, IEEE, pages 143-152.
• 45: Symbolic Computation Group, University of Waterloo. Maple 4.0 Reference Manual. Waterloo, Canada, 1985.

INDEX TERMS

Primary Classification:
  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING
      Subjects: Computer-aided design (CAD)

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

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Algebraic algorithms
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.10 Vision and Scene Understanding
            Subjects: Representations, data structures, and transforms; Modeling and recovery of physical attributes
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations; Modeling packages
      I.3.6 Methodology and Techniques
          Subjects: Languages

General Terms:
Algorithms, Design, Languages, Measurement, Performance, Reliability, Theory