Parallel terrain triangulation

References

• BANERJEE , S. , MOUNT , D. , and ROSENFELD , A. , 1990 , Pyramid computation of neighbor distance statistics in dot patterns. Technical report CS-TR-2429 , University of Maryland , College Park , MD , U.S.A.
   Google Scholar
• BARNHILL , R. E. , 1974 , Smooth interpolation over triangles. In omputer Aided Geometric Design , edited by R. E. Barnhill and R. F. Risenfeld ( New York : Academic Press ), pp. 45 – 70 .
   Google Scholar
• BARRERA , R. , and VAZQUEZ , A. M. , 1984 , A hierarchical method for representing relief . Proceedings Pecora IX Symposium on Spatial Information Technologies/or Remote Sensing Today and Tomorrow, Sioux Falls, South Dakota, U.S.A., October 1984 , pp. 87 – 92 .
   Google Scholar
• BHASKAR , S. K. , ROSENFELD , A. , and Wu , A. Y. , 1988 , Parallel processing of regions represented by linear quadtrees , Computer Vision, Graphics, and Image Processing , 42 (3) , 371 – 380 .
   Google Scholar
• BESTUI. , T. , 1989 , A genera] technique for creating SIMD algorithms on parallel pointer-based quadtrees . Technical Report CAR TR-420, Center for Automation Research , University of Maryland , College Park , MD , U.S.A.
   Google Scholar
• CAVENDISH , J. C. , 1974 , Automation triangulation of arbitrary planar domains for the finite element . International Journal of Numerical Methods in Engineering , 8 , 679 – 696 .
   Google Scholar
• CHEN , Z. T. , and GUEVARA , J. A. , 1987 , Systematic selection of very important points (VIP) from digital terrain model for constructing triangular irregular networks . Proceedings of AUTO-CARTO 8, Baltimore, MD, U.S.A. , edited by N. Chrisman ( Falls Church: American Congress of Surveying and Mapping ), pp. 50 – 60 .
   Google Scholar
• CHEN , Z. T. , and TOBLER , W. R. , 1986 , Quadtree representation of digital terrain , Proceedings AUTO-CARTO 7, London, UK, September 1986 ,edited by M. Blakemore ( London : Auto-Carto ), pp. 475 – 484 .
   Google Scholar
• CHOW , A. L. , 1980 , Parallel algorithms for geometric problems , Ph.D. dissertation, Department of Computer Science , University of Illinois , Urbana , IL , U.S.A.
   Google Scholar
• CHRISTMAN , D. P. , 1983 , Programming the Connection Machine, Master Thesis , Department of Electrical Engineering and Computer Science, M.I.T. , Cambridge , MA , U.S.A.
   Google Scholar
• DADOUN , D. , and KIRKPATRICK , D. G. , 1987 , Parallel processing for efficient subdivision search . In Proceedings ACM Symposium on Computational Geometry , ( New York : ACM Press ), pp. 205 – 214 .
   Google Scholar
• DAVY , J. R. , and DEW , P. M. , 1989, A note on improving the performance of Delaunay triangulation. New Advances in Computer Graphics , edited by R. A. Earnshaw and B. Wyvill ( Tokyo : Springer-Verlag), pp. 209–266.
   Google Scholar
• DE FLORIANI , L. , 1989 , A pyramidal data structure for triangle-based surface description , IEEE Computer Graphics &S Applications , 9 , 67 – 78 .
   Web of Science ®Google Scholar
• DE FLORIANI , L. , FALCIDIENO , B. , NAGY , G. , PIENOVI , C. , 1984 , A hierarchical structure for surface approximation , Computers & Graphics , 8 , 183 – 193 .
   Google Scholar
• DE FLORIANI , L. , FALCIDIENO , B. , and PIENOVI , C. , 1985 , Delaunay-based representation of surfaces defined over arbitrarily shaped domains . Computer Vision, Graphics, and Image Processing , 32 , 127 – 140 .
   Google Scholar
• DE FLORIANI , L. , and PUPPO , E. , 1992 , A hierarchical triangle-based model for terrain description , Theories and Methods of Spatio-Temporal Reasoning in Geographic Space , edited by A. U. Frank , I. Campari , and U. Formentini , Lecture Notes in Computer Science, N. 639 ( Berlin Heidelberg : Springer-Verlag ), pp. 236 – 251 .,
   Google Scholar
• DOUGLAS , D. H. , and PEUCKER , T. K. , 1973 , Algorithms for the reduction of the number of points required to represent a line or its caricature . The Canadian Cartographer , 10 , 112 – 122 .
   Google Scholar
• DWYER , R. , 1989 , Higher dimensional Voronoi diagrams in linear expected time . Proceedings 5th ACM Symposium on Computational Geometry , ( New York : ACM Press ), pp. 326 – 333 .
   Google Scholar
• DYN , N. , LEVIN , D. , and RIPPA , S. , 1990 , Data dependent triangulations for piecewise linear interpolation . IMA Journal of Numerical Analysis , 10 , 137 – 154 .
   Web of Science ®Google Scholar
• EDELSBRUNNER , H. , 1987 , Algorithms in combinatorial geometry ( Berlin Heidelberg : Springer-Verlag ).
   Google Scholar
• FLOWER , R. J. , and LITTLE , J. J. , 1979 , Automatic extraction of irregular nework digital terrain models . Computer Graphics , 13 , 199 – 207 .
   Google Scholar
• GOMEZ , D. , and GUZMAN , A. , 1979 , Digital model for three-dimensional surface representation . Geo-Processing , 1 , 53 – 70 .
   Google Scholar
• GREGORY , J. A. , 1974 , Smooth interpolation without twist constraints . In Computer Aided Geometric Design , edited by R. E. Barnhill , R. F. Risenfeld ( New York : Academic Press ), pp. 71 – 88 .
   Google Scholar
• GUIBAS , L. J. , and STOLFI , J. , 1983 , Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams , Proceedings 15th A.C.M. Conference on the Theory of Computing ( New York : ACM Press ), pp. 221 – 234 .
   Google Scholar
• GUIBAS , L. J. , KNUTH , D. E. , and SHARIR , M. , 1990 , Randomized incremental construction of the Delaunay and Voronoi diagrams . Automata, Languages and Programming , Lecture Notes in Computer Science, N.443 ( Berlin Heidelberg : Springer-Verlag ), pp. 414 – 431 .
   Google Scholar
• HILLIS , W. D. , 1985 . The Connection Machine ( Cambridge , MA : MIT Press ).
   Google Scholar
• HILLIS , W. D. , and STEELE , G. L. , 1986 , Data parallel algorithms . Communications of the ACM , 29 , 1170 – 1183 .
   Web of Science ®Google Scholar
• HUNG , Y. , and ROSENFELD , A. , 1987 , Parallel processing of linear quadtrees on a mesh-connected computer . Technical Report CS-TR-1817 , University of Maryland , College Park. MD , U.S.A.
   Google Scholar
• JOHNSON , E. G. , and ROSENFELD , A. , 1975 , Digital detection of peaks, pits, ridges, and ravines . I.E.E.E. Transactions on Systems, Man, and Cybernetics , 5 , 472 – 480 .
   Google Scholar
• JONES , C. B. , MARK WARE , J. , and BUNDY , G. L. , 1992 , Multiscale spatial modelling with triangulated surfaces , Proceedings 5th International Symposium on Spatial Data Handling, Charleston, SC , U.S.A., 3–7 August, 1992, 2 , edited by P. Bresnahan , E. Corwin , and D. Cowen ( Columbia , SC : IGU Commission on GIS ), pp. 612 – 621 .
   Google Scholar
• LAWSON , C. L. , 1977 , Software for C surface interpolation . In Mathematical Software III , edited by J. R. Rice ( New York : Academic Press ), pp. 161 – 164 .
   Google Scholar
• LEE , J. , 1989 , A drop heuristic conversion method for extracting irregular networks for digital elevation models , Proceedings GIS/LIS'89, Orlando, FL , 1 (Falls Church, VA, U.S.A.: American Congress on Surveying and Mapping, and American Society of Photogrammetry and Remote Sensing; Washington DC: Urban and Regional Information Systems Association, AM/FM International, and Association of American Geographers) ,pp. 33 – 39 .
   Google Scholar
• LEE , J. , 1991 , Comparison of existing methods for building triangular irregular network models , International Journal of Geographical Information Systems , 5 , 267 – 285 .
   Web of Science ®Google Scholar
• LEE , D. T. , and SCHACHTER , B. J. , 1980 , Two algorithms for constructing a Delaunay triangulation . International Journal of Computer and Information Science , 9 , 219 – 242 .
   Google Scholar
• Lu , M. , 1986, Constructing the Voronoi diagram on a mesh connected computer. In Proceedings I.E.E.E. International Conference on Parallel Processing, St. Charles, IL , U.S.A. , August 1986 (New York: I.E.E.E), pp. 806–811.
   Google Scholar
• MARR , D. , and HILDRETH , E. , 1980 , Theory of edge detection . Proceedings Royal Society of London, B , 207 , 187 – 217 .
   Web of Science ®Google Scholar
• MASPAR SYSTEM OVERVIEW: 1990 ( Sunnyvale , CA : MasPar Computer Corporation ).
   Google Scholar
• MEI , G. G. , and Liu , W. , 1986 , Parallel processing for quadtree problems . Proceedings I.E.E.E. International Conference on Parallel Processing, St. Charles , IL , U.S.A. , August 1986 , (New York: I.E.E.E.) , pp. 140 – 147 .
   Google Scholar
• PEUCKER , T. K. , and DOUGLAS , D. H. , 1975 , Detection of surface-specific points by local parallel processing of discrete terrain elevation data . Computer Graphics and Image Processing , 4 , 375 – 387 .
   Google Scholar
• PUPPO , E. , DAVIS , L. S. , DEMENTHON , D. , and TENG , Y. A. , 1991 , Parallel terrain triangulation using the Connection Machine , Technical Report CS-TR-2693 , University of Maryland , College Park MD , U.S.A.
   Google Scholar
• RIPPA , S. , 1990 , Minimal roughness property of Delaunay triangulation . Computer Aided Geometric Design , 7 , 489 – 497 .
   Google Scholar
• RICART , G. , and AGARWALA , A. K. , 1981 , An optimal algorithm for mutual exclusion in computer networks , Communications of the ACM , 24 , 9 – 17 .
   Google Scholar
• SAMET , H. , 1990 , The Design and Analysis of Spatial Data Structures ( Reading , MA : Addison Weslcy ).
   Google Scholar
• SAXENA , S. , BHATT , P. C. P. , and PRASAD , V. C. , 1990 , Efficient VLSI parallel algorithm for delaunay triangulation on orthogonal tree network in two and three dimensions . I.E.E.E. Transactions on Computers , 39 , 400 – 404 .
   Google Scholar
• SCARLATOS , L. L. , 1990 , An automatic critical line detector for digital elevation matrices . Proceedings 1990 ASPRS-ACSM Annual Convention, Denver, Co , U.S.A. , 2 , pp. 43 – 52 .
   Google Scholar
• SCARLATOS , L. L. , and PAVLIDIS , T. , 1990 , Hierarchical triangulation using terrain features . Proceedings I.E.E.E. Conference on Visualization , San Francisco , CA , U.S.A. , ( New York: I.E.E.E. ), pp. 168 – 175 .
   Google Scholar
• SIVAN , R. , and SAMET , H. , 1992 , Algorithms for constructing quadtree surface maps . Proceedings 5th International Symposium on Spatial Data Handling , Charleston , SC , U.S.A. , 3–7 August 1992, 2 , edited by P. Bresnahan , E. Corwin , and D. Cowen (Columbia, SC: IGU Commission on GIS) , pp. 361 – 370 .
   Google Scholar
• SOUTHARD , D. A. , 1991 , Piecewise linear surface models from sampled data . In Scientific Visualization of Physical Phenomena , edited by N. M. Patrikalakis ( Hong Kong : Springer- Verlag ), pp. 667 – 680 .
   Google Scholar
• WANG , C. A. , and TSIN , Y. H. , 1987 , An O(log N) time parallel algorithm for triangulating a set of points in the plane . Information Processing Letters , 25 , 55 – 60 .
   Google Scholar
• WAISON , L. T. , LAFFEY , T. J. , and HARALICK , R. M. , 1985 , Topographic classification of digital image intensity surfaces using generalized splines and the discrete cosine transformation . Computer Vision, Graphics and Image Processing , 29 , 143 – 167 .
   Google Scholar