Thesis Bibliography

[1]

A.V. Aho and J.D. Ullman. Foundations of Computer Science. W.H. Freeman and Company, New York, 1992.

[2]

A.V. Aho, J.E. Hopcroft, and J.D. Ullman. The Design and Analysis of Computer ALgorithms. Addison-Wesley, Reading, Mass., 1974.

[3]

E.M. Arkin, M. Held, J.S.B. Mitchell, and S.S. Skiena. Hamiltonian triangulations for fast rendering. In J. van Leeuwen, editor, Algorithms -- ESA'94, volume 855 of Lecture Notes Comput. Sci., pages 36-47, September 1994.

[4]

E.M. Arkin, M. Held, J.S.B. Mitchell, and S.S. Skiena. Hamiltonian triangulations for fast rendering. Visual Comput., 12(9):429-444, 1996.

[5]

D. Avis. Lower bounds for geometric problems. In Proc. Allerton Conference, pages 35-40, Urbana, IL, October 1980.

[6]

G. Barequet and M. Sharir. Piecewise-linear interpolation between polygonal slices. Comput. Vision Graph. Image Process., 63, 1996. In press.

[7]

G. Barequet and M. Sharir. Piecewise-linear interpolation between polygonal slices. In Proc. 10th Annu. ACM Sympos. Comput. Geom., pages 93-102, 994.

[8]

H. Baumgarten, H. Jung, and K. Mehlhorn. Dynamic point location in general subdivisions. J. Algorithms, 17:342-380, 1994.

[9]

B.K. Bhattacharya and G.T. Toussaint. Efficient algorithms for computing the maximum distance between two finite planar sets. Journal of Algorithms, 4, 1983.

[10]

Prosenjit Bose and Godfried Toussaint. Characterizing and efficiently computing quadrangulations of planar point sets. Comput. Aided Geom. Design, 14:763-785, 1997.

[11]

K.Q. Brown. Geometric transforms for fase geometric algorithms. Technical report, Dep. Comput. Sci., Carnegie-Mellon Univeristy, 1979.

[12]

B. Chazelle and D. P. Dobkin. Detection is easier than computation. In Proc. 12th Annu. ACM Sympos. Theory Comput., pages 146-153, 1980.

[13]

Bernard Chazelle and J. Incerpi. Triangulation and shape-complexity. ACM Trans. Graph., 3(2):135-152, 1984.

[14]

B. Chazelle, H. Edelsbrunner, L.J. Guibas, and M. Sharir. Diameter, width, closest line pair, and parametric searching. In Proc. 8th Annu. ACM Sympos. Comput. Geom., pages 120-129, 1992.

[15]

B. Chazelle, H. Edelsbrunner, L.J. Guibas, and M. Sharir. Diameter, width, closest line pair and parametric searching. Discrete Comput. Geom., 10:183-196, 1993.

[16]

B. Chazelle. Computational geometry and convexity. PhD thesis, Carnegie-Mellon University, 1980.

[17]

B. Chazelle. Algorithms for computing depths and layers. In Proc. Allerton Conf. Commun. Control Comput., pages 427-436, 1983.

[18]

B. Chazelle. On the convex layers of a planar set. IEEE Trans. Inform. Theory, IT-31:509-517, 1985.

[19]

B. Chazelle. Triangulating a simple polygon in linear time. Discrete Comput. Geom., 6:485-524, 1991.

[20]

S. W. Cheng and R. Janardan. New results on dynamic planar point location. SIAM J. Comput., 21:972-999, 1992.

[21]

F. Chin and C. A. Wang. Optimal algorithms for the intersection and the minimum distance problems between planar polygons. IEEE Trans. Comput., C-32(12):1203-1207, 1983.

[22]

K. L. Clarkson, R. E. Tarjan, and C. J. Van Wyk. A fast Las Vegas algorithm for triangulating a simple polygon. Discrete Comput. Geom., 4:423-432, 1989.

[23]

S.A. Cook and R.A. Reckhow. Time bounded random access machines. J. Computer and Systems Sciences, 7(4):354-375, 1973.

[24]

T.H. Cormen, C.E. Leiserson, and R.L. Rivest. Introduction to Algorithms. MIT Press, Cambridge, Massachusetts, 1990.

[25]

A.A.N. DePano. Rotating Calipers revisited: optimal polygonal enclosures in optimal time. In Proc. ACM South Central Regional Conference, Lafayette, LA, November 1987.

[26]

R.O. Duda and P.E. Hart. Pattern Classification and Scene Analysis. Wiley, New York, 1973.

[27]

H. Edelsbrunner, M. H. Overmars, and D. Wood. Graphics in Flatland: A case study. In F. P. Preparata, editor, Computational Geometry, volume 1 of Adv. Comput. Res., pages 35-59. JAI Press, London, England, 1983.

[28]

H. Edelsbrunner. On computing the extreme distance between two convex polygons. Technical Report F96, Inst. Informationsverarb., Tech. Univ. Graz, Graz, Austria, 1982.

[29]

H. Everett, W. Lenhart, M. H. Overmars, T. Shermer, and J. Urrutia. Strictly convex quadrilateralizations of polygons. In Proc. 4th Canad. Conf. Comput. Geom., pages 77-83, 1992.

[30]

A. Fournier and D. Y. Montuno. Triangulating simple polygons and equivalent problems. ACM Trans. Graph., 3(2):153-174, 1984.

[31]

R. L. Francis and J. A. White. Facility Layout and Location. Prentice Hall, Englewood Cliffs, NJ, 1974.

[32]

H. Freeman and R. Shapira. Determining the minimum-area encasing rectangle for an arbitrary closed curve. Comm. A.C.M., 18:409-413, July 1975.

[33]

M. R. Garey, D. S. Johnson, F. P. Preparata, and R. E. Tarjan. Triangulating a simple polygon. Inform. Process. Lett., 7:175-179, 1978.

[34]

U. Grenander. Pattern Synthesis. Springer-Verlag, New York, 1976.

[35]

F. C. A. Groen, P. W. Verbeek, N. DeJong, and J. W. Klumper. The smallest box around a package. Pattern Recogn., 14(1-6):173-178, 1981.

[36]

Leonidas J. Guibas and F. F. Yao. On translating a set of rectangles. In F. P. Preparata, editor, Computational Geometry, volume 1 of Adv. Comput. Res., pages 61-77. JAI Press, London, England, 1983.

[37]

L.J. Guibas, L. Ramshaw, and J. Stolfi. A kinetic framework for computational geometry. In Proc. 24th Annu. IEEE Sympos. Found. Comput. Sci., pages 100-111, 1983.

[38]

E. Heighway. A mesh generator for automatically subdividing irregular polygons into quadrilaterals. IEEE Trans. Magn., 19(6):2535-2538, 1983.

[39]

J. Hershberger and S. Suri. Applications of a semi-dynamic convex hull algorithm. In Proc. 2nd Scand. Workshop Algorithm Theory, volume 447 of Lecture Notes Comput. Sci., pages 380-392. Springer-Verlag, 1990.

[40]

J. Hershberger and S. Suri. Applications of a semi-dynamic convex hull algorithm. BIT, 32:249-267, 1992.

[41]

S. Hertel and K. Mehlhorn. Fast triangulation of simple polygons. In Proc. 4th Internat. Conf. Found. Comput. Theory, volume 158 of Lecture Notes Comput. Sci., pages 207-218. Springer-Verlag, 1983.

[42]

M. E. Houle and G.T. Toussaint. Computing the width of a set. IEEE Trans. on Pattern Analysis and Machine Intelligence, 10(5):761-765, September 1988.

[43]

K. Ichida and T. Kiyono. Segmentation of plane curves. Trans. Elec. Commun. Eng., Japan, 58-D:689-696, 1975.

[44]

H. Imai and M. Iri. Polygonal approximations of a curve: Formulations and solution algorithms. In G.T. Toussaint, editor, Computational Morphology. North-Holland, Amsterdam, The Netherlands, 1988.

[45]

B. P. Johnston, J. M. Sullivan, and A. Kwasnik. Automatic conversion of triangular finite meshes to quadrilateral elements. Internat. J. Numer. Methods Eng., 31(1):67-84, 1991.

[46]

J. Kahn, M. M. Klawe, and D. Kleitman. Traditional galleries require fewer watchmen. SIAM J. Algebraic Discrete Methods, 4:194-206, 1983.

[47]

J. M. Keil and J.-R. Sack. Minimum decompositions of polygonal objects. In G. T. Toussaint, editor, Computational Geometry, pages 197-216. North-Holland, Amsterdam, Netherlands, 1985.

[48]

D. G. Kirkpatrick, M. M. Klawe, and R. E. Tarjan. Polygon triangulation in O(n log log n) time with simple data structures. In Proc. 6th Annu. ACM Sympos. Comput. Geom., pages 34-43, 1990.

[49]

D.E. Knuth. Fundamental Algorithms, volume 1 of The Art of Computer Programming. Addison-Wesley, second edition, 1973.

[50]

D.E. Knuth. Big omicron and big omega and big theta. ACM SIGACT News, 8(2):18-23, 1976.

[51]

Y. Kurozumi and W.A. Davis. Polygonal approximation by the minimax method. Comput. Graphics Image Processing, 19:248-264, 1982.

[52]

D.T. Lee. Personal communication, 1998.

[53]

N. J. Lennes. Theorems on the simple finite polygon and polyhedron. Amer. J. Math., 33:37-62, 1911.

[54]

W. Lipski, Jr., E. Lodi, F. Luccio, C. Mugnai, and L. Pagli. On two-dimensional data organization , Part II. Fundam. Inform., 2:245-260, 1979.

[55]

T. Lozano-Pérez and M.A. Wesley. An algorithm for planning collision-free paths among polyhedral obstacles. Commun. ACM, 22:560-570, 1979.

[56]

A. Lubiw. Decomposing polygonal regions into convex quadrilaterals. In Proc. 1st Annu. ACM Sympos. Comput. Geom., pages 97-106, 1985.

[57]

M. McKenna and G. T. Toussaint. Finding the minimum vertex distance between two disjoint convex polygons in linear time. Comp. & Maths. with Appls., 11(12):1227-1242, 1985.

[58]

T. Ohtsuki. Minimum dissection of rectilinear polygons. In Proc. IEEE Symp. on Circuits and Systems, pages 1210-1213, 1982.

[59]

A. Okabe, B. Boots, and K. Sugihara. Spatial Tessellations: Concepts and Applications of Voronoi Diagrams. John Wiley & Sons, Chichester, UK, 1992.

[60]

J. O'Rourke, C.-B. Chien, T. Olson, and D. Naddor. A new linear algorithm for intersecting convex polygons. Comput. Graph. Image Process., 19:384-391, 1982.

[61]

J. O'Rourke. An on-line algorithm for fitting straight lines between data ranges. Commun. ACM, 24:574-578, 1981.

[62]

J. O'Rourke. Computational Geometry in C. Cambridge University Press, 1994.

[63]

F. P. Preparata and S. J. Hong. Convex hulls of finite sets of points in two and three dimensions. Commun. ACM, 20:87-93, 1977.

[64]

F.P. Preparata and M.I. Shamos. Computational Geometry: an Introduction. Springer-Verlag, New York, 1985.

[65]

F. P. Preparata and R. Tamassia. Fully dynamic point location in a monotone subdivision. SIAM J. Comput., 18:811-830, 1989.

[66]

J. Robert and G.T. Toussaint. Computational geometry and facility location. Technical Report SOCS 90.20, McGill University, School of Computer Science, Montreal, PQ, 1990.

[67]

J.-M. Robert and G. Toussaint. Linear approximation of simple objects. Comput. Geom. Theory Appl., 4:27-52, 1994.

[68]

J.-R. Sack and G. T. Toussaint. A linear-time algorithm for decomposing rectilinear polygons into convex quadrilaterals. In Proc. 19th Allerton Conf. Commun. Control Comput., pages 21-30, 1981.

[69]

J.-R. Sack and G. T. Toussaint. Guard placement in rectilinear polygons. In G. T. Toussaint, editor, Computational Morphology, pages 153-175. North-Holland, Amsterdam, Netherlands, 1988.

[70]

W. J. Schroeder and M. S. Shephard. Geometry-based fully-automatic mesh generation and the Delaunay triangulation. Internat. J. Numer. Methods Eng., 26(11):2503-2515, 1988.

[71]

J. T. Schwartz. Finding the minimum distance between two convex polygons. Inform. Process. Lett., 13:168-170, 1981.

[72]

M. I. Shamos and D. Hoey. Geometric intersection problems. In Proc. 17th Annu. IEEE Sympos. Found. Comput. Sci., pages 208-215, 1976.

[73]

M. I. Shamos. Problems in computational geometry. Technical report, Dept. Comput. Sci., Carnegie-Mellon Univ., Pittsburgh, PA, 1977.

[74]

M.I. Shamos. Computational geometry. PhD thesis, Yale University, 1978.

[75]

R. E. Tarjan and C. J. Van Wyk. An O(n log log n)-time algorithm for triangulating a simple polygon. SIAM J. Comput., 17:143-178, 1988.

[76]

G.T. Toussaint and B.K. Bhattacharya. Optimal algorithms for computing the minimum distance between two finite planar sets. In Proc. Fifth International Congress of Cybernetics and Systems, Mexico City, August 1981.

[77]

G.T. Toussaint and J.A. McAlear. A simple O(n log n) algorithm for finding the maximum distance between two finite planar sets. Pattern Recognition Letters, 1:21-24, October 1982.

[78]

G.T. Toussaint. Pattern recognition and geometrical complexity. In Proc. Fifth International Conference on Pattern Recognition, pages 1324-1347, Miami Beach, December 1980.

[79]

G. T. Toussaint. Computational geometric problems in pattern recognition. In J. Kittler, K. S. Fu, and L. F. Pau, editors, Pattern Recognition Theory and Application, pages 73-91. D. Reidel Publishing Company, Boston, MA, 1982.

[80]

G.T. Toussaint. Solving geometric problems with the `rotating calipers'. In Proc. MELECON, Athens, Greece, 1983.

[81]

G. T. Toussaint. An optimal algorithm for computing the minimum vertex distance between two crossing convex polygons. In Proc. IEEE Internat. Conf. Pattern Recogn., pages 465-467, 1984.

[82]

G. T. Toussaint. An optimal algorithm for computing the minimum vertex distance between two crossing convex polygons. Computing, 32:357-364, 1984.

[83]

G. T. Toussaint. A simple linear algorithm for intersecting convex polygons. Visual Comput., 1:118-123, 1985.

[84]

G.T. Toussaint. Movable separability of sets. In G.T. Toussaint, editor, Computational Geometry, pages 335-375. North-Holland, Amsterdam, The Netherlands, 1985.

[85]

G.T. Toussaint. New results in computational geometry relevant to pattern recognition in practice. In E.S. Gelsema and L.N. Kanal, editors, Pattern Recognition in Practice II, pages 135-146. North-Holland, Amsterdam, Netherlands, 1986.

[86]

G.T. Toussaint. An output-sensitive polygon triangulation algorithm. In Proc. of the 8th Internat. Conf. on Computer Graphics, pages 443-446, 1990.

[87]

Y. F. Wang and J. K. Aggarwal. Surface reconstruction and representation for 3-d scenes. Pattern Recognition, 19:197-207, 1986.

[88]

T. Wang. A C²-quintic spline interpolation scheme on triangulation. Comput. Aided Geom. Design, 9:379-386, 1992.

[89]

S. K. Wismath. Triangulations: An algorithmic study. M.Sc. thesis, Dept. Comput. Inform. Sci., Queen's Univ., Kingston, ON, July 1980. Report 80-106.

[90]

I.M. Yaglom and V.G. Boltyanskii. Convex Figures. Holt, Rinehart and Winston, New York, 1961.

[91]

P. Yoeli. Compilation of data for computer-assisted relief cartography. In J. C. Davis and M.J. McCullagh, editors, Display and Analysis of Spatial Data, pages 352-367. Wiley, New York, 1995.