Date: Tuesday, 14-Jan-97 23:53:24 GMT Server: NCSA/1.1 MIME-version: 1.0 Content-type: text/html Last-modified: Monday, 30-Dec-96 16:50:10 GMT Recent Papers of Joe Mitchell

Selected Papers of Joe Mitchell





J.S.B. Mitchell (1996):
``Shortest Paths and Networks''
Draft of a survey chapter for the CRC Handbook on Computational Geometry.
Feedback is greatly encouraged.

J.S.B. Mitchell (1996):
``Guillotine Subdivisions Approximate Polygonal Subdivisions:
Part II -- A simple polynomial-time approximation scheme for geometric k-MST, TSP, and related problems''

Manuscript, April 1996. (Revised July, 1996)
PostScript color transparencies of talk.

J.S.B. Mitchell (1996):
``Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple New Method for the Geometric k-MST Problem''.
Appears in 7th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA'96),
Atlanta, GA, USA, Jan 28-30, 1996, pages 402--408.
(See journal version below.) Part I of two; see part II above.
PostScript color transparencies of talk.

J.S.B. Mitchell, A. Blum, P. Chalasani, S. Vempala (1996):
``A Constant-Factor Approximation Algorithm for the Geometric k-MST Problem in the Plane''
Journal version of above; last revision July 1996.

E.M. Arkin, Y-J. Chiang, J.S.B. Mitchell, S.S. Skiena, and T-C. Yang (1997):
``On the Maximum Scatter TSP''
8th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA'97), to appear, New Orleans, LA, USA, Jan 5-7, 1997, pages ??.
Full paper submitted to JACM

J.S.B. Mitchell (1996):
``On Some Applications of Computational Geometry in Manufacturing and Virtual Environments''
Abstract of talk ( transparencies) at the Workshop on Applied Computational Geometry
Part of FCRC'96, Philadelphia, May 27-28, 1996.

E.M. Arkin, M. Held, J.S.B. Mitchell, S.S. Skiena (1995):
``Recognizing Polygonal Parts from Width Measurements''
Proc. 7th Canadian Conference on Computational Geometry,
C. Gold, J.-M. Robert (eds.), pp. 199-204; Québec City, Québec, Canada, Aug 10-13, 1995.
To appear, Computational Geometry: Theory and Applications

E.M. Arkin, Y-J. Chiang, M. Held, J.S.B. Mitchell, V. Sacristan, S.S. Skiena, and T-C. Yang (1996):
``On Minimum-Area Hulls''
Proc. European Symposium on Algorithms (ESA'96),
Submitted to, Algorithmica

M. Held, J. Klosowski, J.S.B. Mitchell:
``Evaluation of Collision Detection Methods for Virtual Reality Fly-Throughs''
Proc. 7th Canadian Conference on Computational Geometry,
C. Gold, J.-M. Robert (eds.), pp. 205-210; Québec City, Québec, Canada, Aug 10-13, 1995.

G. Barequet, B. Chazelle, L. Guibas, J.S.B. Mitchell, A. Tal:
``BOXTREE: A Hierarchical Representation for Surfaces in 3D''
EuroGraphics'96,
J. Rossignac and F. Sillion, eds., Blackwell Publishers, Europgraphics Association, Volume 15, (1996), Number 3, pages C-387--C-484.

C. Silva, J.S.B. Mitchell, and A. Kaufman (1996):
``Fast Rendering of Irregular Grids''
ACM-IEEE Symposium on Volume Visualization (VolVis'96), San Francisco, CA, Oct 28-29, 1996, pages 15-22 (color plate, page 97).

E.M. Arkin, M. Held, J.S.B. Mitchell, S.S. Skiena (1994):
``Hamiltonian Triangulations for Fast Rendering''
European Symposium on Algorithms (ESA'94),
Springer-Verlag, LNCS 855, J. van Leeuwen (ed.), pp. 36-47;
Utrecht, The Netherlands, Sep 26-28, 1994.
Full paper appears in The Visual Computer, 12(9), pp. 429--444, 1996.

J.S.B. Mitchell and E.L. Wynters :
``Finding Optimal Bipartitions of Points and Polygons''
Extended abstract in Springer LNCS, Vol. 519, (F. Dehne, J.-R. Sack, N. Santoro, eds.),
Workshop on Algorithms and Data Structures (WADS'91), Ottawa, Ontario, August 14-16, 1991, pp. 202-213.
Full paper (above) is updated and corrects an error in the WADS abstract.

E.M. Arkin, D. Halperin, K. Kedem, J.S.B. Mitchell, and N. Naor:
``Arrangements of Line Segments that Share Endpoints: Single Face Results''
Discrete & Computational Geometry, Vol. 13, Nos. 3-4, pp. 257-270,
Special Volume on discrete geometry dedicated to Laszlo Fejes Toth (J. Pach and I. Barany, eds.), 1995.
Original conference version was in Proc. Seventh Annual ACM Symposium on Computational Geometry,
North Conway, NH, June 10-12, 1991, pp. 324-333. (Conference version incorrectly claimed a bound of O(h log h).)

E.M. Arkin, H. Meijer, J.S.B. Mitchell, D. Rappaport, and S.S. Skiena:
``Decision Trees for Geometric Models''
To appear in the International Journal of Computational Geometry and Applications
An earlier version appears in Proc. Ninth Annual ACM Symposium on Computational Geometry, May, 1993, pp. 368-378.

E.M. Arkin, M. Goodrich, J.S.B. Mitchell, D. Mount, C. Piatko, and S.S. Skiena:
``Point Probe Decision Trees for Geometric Concept Classes'' (two pages of FIGURES are separate)
Workshop on Algorithms and Data Structures, August, 1993, pp. 95-106.

J.S.B. Mitchell, D. Mount, and S. Suri:
``Query-Sensitive Ray Shooting''
Proc. Tenth Annual ACM Symposium on Computational Geometry, June 6-8, 1994, pp. 359-368.
To appear in the International Journal of Computational Geometry and Applications

J.S.B. Mitchell and S. Suri:
``Separation and Approximation of Polyhedral Objects''
Computational Geometry: Theory and Applications 5(1995), 95--114.

J.S.B. Mitchell:
``Approximation Algorithms for Geometric Separation Problems''
Technical Report, 1993. L. J. Guibas, J. E. Hershberger, J. S. B. Mitchell, and J. S. Snoeyink:
``Approximating Polygons and Subdivisions with Minimum Link Paths''
Proc. Second Annual International Symposium on Algorithms (SIGAL), December 16-18, 1991, Taipei, Taiwan, R.O.C., pp. 151--162, Springer Lecture Notes in Computer Science, Vol. 557.
Full paper appears in International Journal of Computational Geometry & Applications Vol. 3, No. 4, December 1993, pp. 383--415.
last modification of this page: Tuesday, October 22, 1996
Joe Mitchell (jsbm@ams.sunysb.edu)