Many other people, primarily my students, worked at least as hard as I did. I am proud to name these students, who obtained postgraduate degrees under my supervision, here.

1. Varol Akman, Shortest Paths Avoiding Polyhedral Obstacles in 3-Dimensional Euclidean Space, 1985. now at Bilkent University, Turkey.

Abstract:

Algebraic and geometric algorithms are presented to solve the general and some specific instances of the following problem which is known as FINDPATH in artificial intelligence: "Given a set of polyhedra and two external points (source and goal), calculate the shortest path between these points under the Euclidean metric, constrained to avoid intersections with the given polyhedra."

The shortest path is a polygonal path connecting the source and the goal, possibly bending at some edges of the given polyhedra while subtending equal entry and exit angles. The general problem can then be solved exactly using symbolic algebra and is based upon finding the real roots of a system of non-linear equations (stating the angular equality conditions) by elimination. If approximate solutions are acceptable this can also be done using numerical methods such as continuation, or using optimization methods to minimize a sum of square roots (expressing the length of the shortest path). In addition, two special cases are solved where there exists a single convex polyhedron, and the source and the goal are on its boundary or exterior. These solutions make use of planar developments of polyhedra and polyhedral visibility.

Two Voronoi-based locus methods are also introduced to solve FINDPATH. These methods use preprocessing to speed up subsequent searches for a shortest path. The first method partitions the boundary of a convex polyhedron given only the source on it so that, for a later goal on the boundary, the shortest path is found efficiently. It makes use of standard point location algorithms for a straight-edge planar subdivision once the partitioning is done. The second method, currently more of a descriptive nature than algorithmic, is based on W. R. Franklin's "Partitioning the Plane to Calculate Minimal Paths to any Goal around Obstructions" Tech. Rep., ECSE Dept., Rensselaer Polytechnic Inst., Troy, NY, Nov. 1982 , and for a given source, partitions the free space around polyhedra into regions (bounded by high-order surfaces) so that the shortest paths for all goals in a given region follow the same sequence of edges of the given polyhedra. This method makes use of a recent spatial point location algorithm for arbitrary algebraic varieties.

Finally, an overview of a workbench (called SP) which implements some of the above and thus allows experimentation with shortest paths is given.

1. William S. Yerazunis, DIS-An Architecture for Fast Lisp Execution, 1987. MERL Cambridge Research.

2. Peter Yick Fai Wu, Polygon Overlay in Prolog, 1987. Roger Morris U.

3. Ernesto Guerrieri, A Methodology for Software Transportability, 1989. Died, 1/4/2007.

4. Mohan Kankanhalli, Techniques for Parallel Geometric Computations, 1990. National University of Singapore.

5. Chandra Narayanaswami, Parallel Processing for Geometric Applications, 1991. Principal RSM, Chief Scientist and Senior Manager, IBM Commerce Research.

6. Clark K. Ray, Representing Visibility for Siting Problems, 1994. formerly US Military Academy, West Pointl

7. Victor Skowronski, Synthesizing Tolerances for Optimal Design Using the Taguchi Quality Loss Function, 1996. TASC, Inc.

8. Michael B Gousie, Contours to Digital Elevation Models: Grid-based Surface Reconstruction Methods, 1998. Wheaton College.

9. Hélio Pedrini, An Adaptive Method for Terrain Surface Approximation Based on Triangular Meshes, 2000. Institute of Computing, University of Campinas, Brazil.

10. Linda Lim, Haptic and Multi-Modal Interaction for Teaching and Designing Basic Controls, 2004. As of 2022 Chair of the Hudson Valley Community College, Department of Computer Science and Mathematics, see https://www.hvcc.edu/about/news/archives/2022/06/three-new-department-chairs-named-in-school-of-stem.html .

11. Metin Inanc, Compressing Terrain Elevation Datasets, 2008.

12. Dan Tracy, Path Planning and Slope Representation on Compressed Terrain, 2009, Sterling Insurance in Cobleskill NY.

13. Chris Stuetzle, Representation and generation of terrain using mathematical modeling, July 2012. Merrimack College.

14. Tsz-Yam (Eddie) Lau, Two-step ODETLAP and induced terrain framework for improved geographical data reconstruction, Nov 2012.

15. Wenli Li, GPU-accelerated terrain processing, Aug 2016.

16. Salles Viana Gomes de Magalhães, Exact and parallel intersection of 3D triangular meshes, Dec 2017. Federal University of Vicosa, Minas Gerais, Brazil.

(including both theses and projects).

1. Leong Shin Loong, Hidden Sphere Algorithm, 1979.

2. Abel Shi Lo, Hidden Surface Algorithm, 1979.

3. Steve Lord, Upgrading of the U.S.M.A. Wargame, 1979.

4. Lih-Chung Chia, Padded List, 1981.

5. Quei-Her Lee, An Algorithm for the Calculation of Polyhedron Coordinates from Dihedral Angles, 1981.

6. Gerald L. Delisle, A Computerized Script Specification System for an Interactive Videodisk Based Maintenance Scenario, 1981.

7. Terrance Nicholson, and

8. Steve Wong, A Tactical Model Simulation for 3-Dimensional Look-Alike Sonar Trainers, 1981.

9. Mark A. Johnson, Computer Controlled Ultrasonic Inspection of Cannon Tubes.

10. Clark Ray, Facilitating the Development of Large Programs on Microcomputer Systems, 1981.

11. Chien-Min Wan, A Computer Program for the Shading Sphere Algorithm, 1981.

12. David Chris Arney, Implementing the Variable Grid Searching Algorithm, 1982.

13. Dipak Shah, The Geometrical Properties of Objects, 1982.

14. Robert Poueau Shen, Geometric Editor for Kepler System, 1982.

15. Frank Kastenholz, Rational Basic Preprocessor, 1982.

16. Kee Hong Lai, Design and Implementation of Algorithms in Solid Modeling Using Rays, 1982.

17. Esther O. Buschak, AEDPAK - Low Level Routines for the AED512, 1982.

18. Lu Chung, Real Time Rigid Body Motion on the Adage GP-435 System, 1983.

19. Robert W. Dworak Jr., and

20. Michael W. Rivenburg, Reconfigurable System Module, 1983.

21. Peter Yick Fai Wu, Modelling Face Details in the Boundary Representation Scheme of Polyhedral Solids, 1983.

22. Philip J. Lohr, Interface and Control Design for a Computer Aided Thermal Engineering Systems, 1983.

23. Joe Ho, A Ratfor Preprocessor for Fortran 77, 1984.

24. Colin Verrilli, One Source Voronoi Diagrams with Barriers - A Computer Implementation, 1984.

25. Karen L. Sonin, A Prototype Development Environment for Real Time Control Applications, 1984.

26. Martin Meyer, Improvement of Software Quality Using a Relational Database, 1984.

27. Naoki Urano, Implementation of a 3-D Surface Digitizing Algorithm, 1984.

28. Scott D. Culp, Spinwriter Tech/Math Wheel Text Formatter, 1984.

29. Chung-Man Felin Fung, DeAnza Software, 1984.

30. Joaquin Bartra, Computer Implementation of 2-D Voronoi Diagrams, 1985.

31. David Kass, Mapping a Hierarchical Block Circuit Description to a True Exploded Network Instance Tree, 1985.

32. Sumitro Samaddar, An Expert System for Photo Interpretation, 1985.

33. Margaret Nichols, A Prolog Implementation of the Graphics Kernel System, 1985.

34. Madeline Morrow, Design and Implementation of a Text Processing System for Personal Computers, 1986.

35. Gautam Shroff, EXPLOT: A Software Tool for Analyzing Expert Systems, 1987.

36. Dave Hamann, Octree Object Creation and Storage, 1987.

37. Rahul Bansal, Debugging, Testing, and Maintaining Expert Systems, 1987.

38. Elissa Gilbert, Software Tools for the Testing and Maintenance of Expert Systems, 1987.

39. Chandrasekhar Narayanaswami, and

40. Manoj Seshan, The Efficiency of Uniform Grids for Computing Intersections, 1987.

41. Mohan Kankanhalli, The Uniform Grid Technique for Fast Line Interaction on Parallel Machines, 1988.

42. Gary A. Crocker, Boundary Evaluation of Solid Models, Algorithm Study and Implementation, 1988.

43. David Sun, Implementation of a Fast Map Overlay Program in C, 1989.

44. Alok Prakash, Using Abstraction Induced by Substitution Partition for Planning, 1987.

45. Ian McLeod, System Design of an Embedded Real Time Simulation/Simulation System, 1990.

46. George Kastrinakis, The Ada Software Architecture of a Distributed, Embedded, Real- Time Simulation/Simulation System, 1990.

47. Venkateshkumar Sivaswami, Point Inclusion Testing in Polygons and Point Location in Planar Graphs Using the Uniform Grid Technique, 1990.

48. James TenBrink, The Maintenance of Voronoi Diagrams Imposed Upon Moving Point Sets, 1991.

49. Thomas G. Nogles, A Software Design Approach for Real-Time Ada-Based Systems, 1991.

50. Tricia J. Beardslee, The Hierarchical Hybrid Parallel Computing Method for Message- Passing Architectures and its Application to CT Reconstruction, 1991.

51. Dragana Pavlovic, InterViews Tutorial, 1991.

52. Andrew Oelkers, An Automatic Software Unit Test Generator, 1992.

53. Lori Schimanski, The Use of Software Scheduling Algorithms in the Development of Real Time Ada Software, 1992.

54. Cheok Hee, The Cross Area Problem in Cartography, 1992.

55. Chris Volpe, Visualization, Animation, and Graphics Environment, 1992.

56. Sriram Gopalakrishnan, Volume of Material Drilled by an NC Drill Using Union of Polyhedra, 1995.

57. Kenneth B. Martinez, Computer Representation of Terrain Mappings, 1995.

58. Michael Martincich, Development of Contour Following Algorithms to Implement Inexpensive Immersion Based Ultrasonic Inspections of Turbine-Generator Components, 1995.

59. Nils S Loehner-Boeffel, Implementing Network Security, 1996.

60. Christian Vogt, Siting Multiple Observers On Digital Elevation Maps Of Various Resolutions 2004.

61. Jared Stookey, *Parallel Terrain Compression and Reconstruction*, 2008.

62. Nathan LeStage, Genetic Algorithm Tuning: Overcoming Diversity Loss in Tournament Selection, 2009.

63. Luke Perkins, An Integrated Approach to Choke Point Detection and Region Decomposition, 2010.

64. Jeffrey Sult, Computational analysis of first-person shooter levels, Apr 2011.

65. Michael J Snyder, Using The HTML5 Canvas Element For A Web-Based Multi-User Painting Application, Apr 2011.

66. Dan Benedetti, CUDA-accelerated ODETLAP: A parallel compression implementation for multidimensional data, May 2014. Thesis.

67. David Hedin, NearptD: A Parallel Implementation of Exact Nearest Neighbor Search using a Uniform Grid, July 2016. Project.