Selected Papers of Joe Mitchell

Acknowledgement

This material is based upon work supported by the National Science Foundation under Grant Nos. CCF-0528209, CCF-0431030, ACI-0328930, CCR-0098172, CCR-9732220, CCR-9504192. Some of this research is also supported by grants from NASA (NAG2-1325,NAG2-1620), the US-Israel Binational Science Foundation (No. 2000160), and grants from Honda, Metron Aviation, Sandia, Sun Microsystems, HRL Labs, Northrop-Grumman, Boeing, Seagull Technologies, and Bridgeport Machines.

Joseph S. B. Mitchell, A Constant-Factor Approximation Algorithm for {TSP} with Neighborhoods in the Plane, Submitted.

Alon Efrat, Sandor P. Fekete, Poornananda R. Gaddehosur, Joseph S. B. Mitchell, Valentin Polishchuk, and Jukka Suomela. Improved Approximation Algorithms for Relay Placement, ESA, 2008.

Esther M. Arkin, Joseph S. B. Mitchell, and Valentin Polishchuk. Maximum Thick Paths in Static and Dynamic Environments, Proc. 24th Annual ACM Symposium on Computational Geometry, June 2008.

Joondong Kim, Joseph S. B. Mitchell, Valentin Polishchuk, and Arto Vihavainen. Routing a Maximum Number of Disks through a Scene of Moving Obstacles, Proc. 24th Annual ACM Symposium on Computational Geometry (Multimedia Session), June, 2008.

Rik Sarkar, Xianjin Zhu, Jie Gao, and Joseph S. B. Mitchell. Light-weight Contour Tracking in Wireless Sensor Networks, INFOCOM'08.

Rik Sarkar, Xianjin Zhu, Jie Gao, Leonidas J. Guibas, and Joseph S. B. Mitchell. Iso-Contour Queries and Gradient Routing with Guaranteed Delivery in Sensor Networks, INFOCOM'08.

Amitabh Basu, Joseph S. B. Mitchell, and Girishkumar Sabhnani. Geometric Algorithms for Optimal Airspace Design and Air Traffic Controller Workload Balancing, ALENEX 2008.

Joseph S. B. Mitchell and Valentin Polishchuk. Thick Non-Crossing Paths and Minimum-Cost Flows in Polygonal Domains, Proc. 23rd Symposium on Computational Geometry (SoCG'07), pp.56--65, 2007.

Yoav Amit, Joseph S. B. Mitchell, and Eli Packer. Locating Guards for Visibility Coverage of Polygons, Proc. Ninth Workshop on Algorithm Engineering and Experiments (ALENEX'07), pp.~120-134, Proceedings in Applied Mathematics. SIAM, 2007.

Joseph S. B. Mitchell. A PTAS for TSP with Neighborhoods Among Fat Regions in the Plane, SODA 2007.

Yue Wang, Jie Gao, Joseph S. B. Mitchell. Boundary Recognition in Sensor Networks by Topological Methods, Proc. 12th Annual ACM Conference on Mobile Computing and Networking (MobiCom 2006), 2006.

Esther M. Arkin, Michael A. Bender, Joseph S. B. Mitchell, and Valentin Polishchuk. The Snowblower Problem, Proc. Seventh International Workshop on the Algorithmic Foundations of Robotics (WAFR'06), 2006.

Amitabh Basu, Jie Gao, Joseph S. B. Mitchell, and Girishkumar Sabhnani. Distributed Localization Using Noisy Distance and Angle Information, MobiHoc '06: Proc. 7th ACM International Symposium on Mobile Ad Hoc Networking and Computing, pp. 262-273, May 2006.

Jimmy Krozel, Changkil Lee, and Joseph S. B. Mitchell. Turn-Constrained Route Planning for Avoiding Hazardous Weather, Air Traffic Control Quarterly, 2006.

Robert Connelly, Erik D. Demaine, Martin L. Demaine, Sandor P. Fekete, Stefan Langerman, Joseph S. B. Mitchell, Ares Ribo, and Guenter Rote. Locked and Unlocked Chains of Planar Shapes, Proc. 22nd Annual ACM Symposium on Computational Geometry, pp. 61-70, 2006.

Esther M. Arkin, Gill Barequet, and Joseph S. B. Mitchell. Algorithms for Two-Box Covering, Proc. 22nd Annual ACM Symposium on Computational Geometry, pp. 459-467, 2006.

Helmut Alt, Esther M. Arkin, Herve Bronnimann, Jeff Erickson, Sandor P. Fekete, Christian Knauer, Jonathan Lenchner, Joseph S. B. Mitchell, and Kim Whittlesey. Minimum-Cost Coverage of Point Sets by Disks, Proc. 22nd Annual ACM Symposium on Computational Geometry, pp. 449-458, 2006.

Esther M. Arkin, Ferran Hurtado, Joseph S. B. Mitchell, Carlos Seara, and Steven S. Skiena, Some Lower Bounds on Geometric Separability Problems International Journal of Computational Geometry and Applications 161):1-26, 2006.

Olaf Hall-Holt, Matthew J. Katz, Piyush Kumar, Joseph S. B. Mitchell and Arik Sityon, Finding Large Sticks and Potatoes in Polygons Proc. 17th ACM-SIAM Symposium on Discrete Algorithms, 2006.

Paz Carmi, Matthew J. Katz, and Joseph S. B. Mitchell, The Minimum-Area Spanning Tree Problem Proc. 9th Workshop Algorithms Data Struct., 2005, LNCS Vol. 3608, pages 195-204.

Ovidiu Daescu, Joseph S. B. Mitchell, Simeon Ntafos, James D. Palmer, and Chee K. Yap, $k$-Link Shortest Paths in Weighted Subdivisions, Proc. 9th Workshop Algorithms Data Struct., 2005, LNCS Vol. 3608, pages

Boaz Ben-Moshe, Matthew J. Katz, and Joseph S. B. Mitchell, A Constant-Factor Approximation Algorithm for Optimal Terrain Guarding In Proc. 16th ACM-SIAM Symposium on Discrete Algorithms, 2005.

Alon Efrat, Sariel Har-Peled, and Joseph Mitchell,
Approximation Algorithms for Two Optimal Location Problems in Sensor Networks, Proc. BroadNets 2005: Second INternational Conference on Broadband Networks. (Presented also in the 2004 Fall Workshop on Computational Geometry)

Joseph S. B. Mitchell and Micha Sharir,
New Results on Shortest Paths in Three Dimensions, Proc. 20th Annual ACM Symposium on Computational Geometry, pp. 124-133, June 9-11, 2004.

Boaz Ben-Moshe, Olaf Hall-Holt, Matthew Katz, and Joseph S. B. Mitchell,
Computing the Visibility Graph of Points Within a Polygon, Proc. 20th Annual ACM Symposium on Computational Geometry, pp. 27-35, June 9-11, 2004.

Matya Katz, Joseph S. B. Mitchell, and Yuval Nir
Orthogonal Segment Stabbing, European Workshop on Computational Geometry, 2003, Journal version appears in CGTA 30(2): 197-205, 2005.

Esther M. Arkin, Michael A. Bender, Dongdong Ge, Simai He, and Joseph S. B. Mitchell, Improved Approximation Algorithms for the Freeze-Tag Problem, Proc. 15th Annual ACM Symposium on Parallelism in Algorithms and Architecture, pp. 295--303, June 2003.

Moshe Dror, Alon Efrat, Anna Lubiw, and Joseph S. B. Mitchell: ``Touring a Sequence of Polygons'', Proc. 35th ACM Symposium on Theory of Computing (STOC 2003), San Diego, CA, June 9-11, 2003, pp. 473--482.

Marcelo Sztainberg, Esther M. Arkin, Michael A. Bender, and Joseph S. B. Mitchell:
``Analysis of Heuristics for the Freeze-Tag Problem'', Proc. Eighth Scandinavian Workshop on Algorithm Theory (SWAT 2002), July 3-5, 2002, Turku, Finland.

Piyush Kumar, Joseph S. B. Mitchell, and Alper Yildirim:
Computing Core-Sets and Approximate Smallest Enclosing HyperSpheres in High Dimensions, Proc. Fifth Workshop on Algorithm Engineering and Experiments, ALENEX '03, pp. 45--55, 2003.

Regina Estkowski, Joseph S. B. Mitchell, and Xinyu Xiang:
Optimal Decomposition of Polygonal Models into Triangle Strips, ( pdf file), In Proc. 18th Annual ACM Symposium on Computational Geometry, pp. 254-263, June, 2002.

Boaz Ben-Moshe, Matthew J. Katz, Joseph S. B. Mitchell, and Yuval Nir:
Visibility Preserving Terrain Simplification -- An Experimental Study, In Proc. 18th Annual ACM Symposium on Computational Geometry, pp. 303-311, June, 2002. Full version appears in special issue of Computational Geometry: Theory and Applications, 28(2-3):175-190, 2004.

Esther M. Arkin, Michael A. Bender, Sandor P. Fekete, Joseph S. B. Mitchell, and Martin Skutella:
``The Freeze-Tag Problem: How to Wake Up a Swarm of Robots'', Proc. 13th ACM-SIAM Symposium on Discrete Algorithms, San Francisco, CA, January 6-8, 2002, pages 568--577. journal version, in Algorithmica, 46(2):193-221, 2006.

Reaching Folded States of a Rectangular Piece of Paper, Erik D. Demaine and Joseph S. B. Mitchell, in Proceedings of the 13th Annual Canadian Conference on Computational Geometry, August 13-15, 2001. pp. 73-75.

Esther M. Arkin, Sandor P. Fekete, and Joseph S. B. Mitchell:
``An Algorithmic Study of Manufacturing Paperclips and Other Folded Structures'', Under final revision for a special issue of Computational Geometry: Theory & Applications, 2002.

Boaz Ben-Moshe, Matthew J. Katz, Joseph S. B. Mitchell:
Computing the $L_1$-Center in the Presence of Rectangular Obstacles, Proc. 17th ACM Symposium on Computational Geometry, June 3-5, 2001.

Regina Estkowski and Joseph S. B. Mitchell:
Simplifying a Polygonal Subdivision While Keeping it Simple, (or try the pdf file if you have problems downloading the compressed ps). Proc. 17th ACM Symposium on Computational Geometry, June 3-5, 2001.

Adrian Dumitrescu, Joseph S. B. Mitchell, and Micha Sharir:
Binary Space Partitions for Axis-Parallel Segments, Rectangles, and Hyperrectangles, Proc. 17th ACM Symposium on Computational Geometry, June 3-5, 2001.

Esther M. Arkin, Michael A. Bender, Erik D. Demaine, Martin L. Demaine, Joseph S. B. Mitchell, Saurabh Sethia, and Steven S. Skiena:
"When Can You Fold a Map?" Submitted for publication, 2000. These results were featured in a recent article in Science News, as well as other popular press articles: Boston Globe article on Erik, article in Nature News Service (see also SunSpot.com)

Adrian Dumitrescu and Joseph S. B. Mitchell:
"Approximation algorithms for TSP with neighborhoods in the plane" Proc. 12th ACM-SIAM Sympos. Discrete Algorithms (SODA'2001), January, 2001. journal version, in Journal of Algorithms, 48:135-159, 2003. (SODA'01 special issue).

Esther M. Arkin, Michael A. Bender, Erik D. Demaine, Sandor P. Fekete, Joseph S. B. Mitchell, and Saurabh Sethia:
"Optimal Covering Tours with Turn Costs" Proc. 12th ACM-SIAM Sympos. Discrete Algorithms (SODA'2001), January, 2001. A journal submission version is on the arXiv

Alon Efrat, Leonidas J. Guibas, Sariel Har-Peled, David C. Lin, Joseph S. B. Mitchell, and T. M. Murali:
"Sweeping Simple Polygons with a Chain of Guards", Proc. 11th ACM-SIAM Sympos. Discrete Algorithms (SODA'2000), pp. 927--936, 2000.

E.M. Arkin, Michael A. Bender, Joseph S. B. Mitchell, and Steven S. Skiena:
``The Lazy Bureaucrat Scheduling Problem", Proc. 1999 Workshop on Algorithms and Data Structures (WADS '99), August 11-14, 1999, pp. 122--133. Full version appears in Information and Computation Volume 184, Issue 1 , 10 July 2003, Pages 129-146.

J.S.B. Mitchell:
``Geometric Shortest Paths and Network Optimization''
Draft of a survey chapter for the Handbook of Computational Geometry, Elsevier Science, (J.-R. Sack and J. Urrutia, eds.), 2000. (Now appears as Chapter 15, pages 633--701.)
Feedback is greatly encouraged. Please let me know of errors/omissions. I will try to keep it updated, as new results appear.
This survey is an extended, expanded, and updated version of the short survey: ``Shortest Paths and Networks,'' Chapter 24 (pp. 445--466) in the CRC Handbook of Discrete and Computational Geometry, CRC Press LLC, (Jacob E. Goodman and Joseph O'Rourke, eds.), 1997.

Shakhar Smorodinsky, Micha Sharir, and Joseph S. B. Mitchell (1998):
Sharp Bounds on Geometric Permutations of Pairwise Disjoint Balls in $\R^d$, Proc. 15th ACM Symposium on Computational Geometry, pp. 400-406, June 1999. Now appears in the special issue of Discrete and Computational Geometry, 23:247--259 (2000).

Xinyu Xiang, Martin Held, and Joseph S. B. Mitchell (1998):
``Fast and Effective Stripification of Polygonal Surface Models,'' Published in: ACM Symposium on Interactive 3D Graphics, 1999. ( color plate)
See also our page on stripification: Stripification of polygonal surface models for fast rendering: FTSG

E.M. Arkin, Giri Narasimhan, and J. S. B. Mitchell (1997):
``Resource-Constrained Geometric Network Optimization'' Proc. Fourteenth ACM Symposium on Computational Geometry, June 6-10, 1998, pages 307--316.

Erik D. Demaine, Martin L. Demaine, and J. S. B. Mitchell (1998):
``Folding Flat Silhouettes and Wrapping Polyhedral Packages: New Results in Computational Origami,'' Proc. 15th ACM Symposium on Computational Geometry, pp. 105-114, June 1999. Now appears in journal form as an invited paper in the special issue of Computational Geometry: Theory & Applications, 16(1), pp. 3-21, 2000.

J.S.B. Mitchell,
``A Geometric Shortest Path Problem, with Application to Computing a Longest Common Subsequence in Run-Length Encoded Strings'', Technical Report, 1997.

Y-J. Chiang, J. T. Klosowski, C. Lee, and J. S. B. Mitchell (1997):
``Geometric Algorithms for Conflict Detection/Resolution in Air Traffic Management'', 36th IEEE Conference on Decision and Control, December 10-12, 1997, San Diego, CA, pages 1835-1840.

C. Silva and J.S.B. Mitchell (1997):
``The Lazy Sweep Ray Casting Algorithm for Rendering Irregular Grids''
IEEE Transactions on Visualization and Computer Graphics, Volume 3, Number 2, June, 1997. (A paper based on an improvement to the VolVis'96 paper below.)

M.T. Goodrich, J.S.B. Mitchell, and M.W. Orletsky, ``Practical Methods for Approximate Geometric Pattern Matching under Rigid Motions'', Proc. 10th ACM Symposium on Computational Geometry, June 6-8, 1994, pp.~103--112. Journal version ( Approximate Geometric Pattern Matching under Rigid Motions) appears now in IEEE Trans. on Pattern Analysis and Machine Intelligence, Volume 21, Number 4, April 1999, pp 371-379.

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).

J.S.B. Mitchell (1997):
``Computational Geometry Problems in the Real (and Virtual) World''
PostScript slides for talk at DREI'97 on selected elementary applications of CG

J.S.B. Mitchell:
Introduction: Special Issue of Algorithmica devoted to Computational Geometry and Manufacturing
PostScript 3-page introduction to a special issue editted by J. Mitchell (due out in 1997)

J.S.B. Mitchell (1997):
``Guillotine Subdivisions Approximate Polygonal Subdivisions:
Part III -- Faster polynomial-time approximation schemes for geometric network optimization''
Manuscript, April 1997.
Appears as an invited talk entitled ``Approximation Algorithms for Geometric Optimization Problems,'' in the Proceedings (available on-line): Ninth Canadian Conference on Computational Geometry, Queen's University, Kingston, Canada, August 11-14, 1997, pp. 229--232.

J.S.B. Mitchell (1996):
``Guillotine Subdivisions Approximate Polygonal Subdivisions:
A simple polynomial-time approximation scheme for geometric TSP, k-MST, and related problems''
Manuscript, April 1996. (Revised July, 1996; May, 1997)
SIAM J. Computing , Vol. 28, No. 4, pp. 1298-1309, 1999.
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 April 1997. Appears now in SICOMP, Volume 28, Number 3, pages 771-781.

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), New Orleans, LA, USA, Jan 5-7, 1997, pages 211--220.

Sandor P. Fekete and Joseph S. B. Mitchell:
Terrain Decomposition and Layered Manufacturing, in International Journal of Computational Geometry and Applications, 11(6):647-668, 2001.

E.M. Arkin, Sandor P. Fekete, Joseph S. B. Mitchell:
``Approximation Algorithms for Lawn Mowing and Milling''
CGTA 17(1-2), October 2000, pp. 25--50.

S. Kapoor, S. N. Maheshwari, and J.S.B. Mitchell:
``An Efficient Algorithm for Euclidean Shortest Paths Among Polygonal Obstacles in the Plane''
Discrete and Computational Geometry, 18:377--383 (1997).

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.

A. Tamir and J.S.B. Mitchell (1995):
``A Maximum b-Matching Problem Arising from Median Location Models with Applications to the Roommates Problem''
Manuscript, 1995. Published in, Mathematical Programming 80 (1998) 171--194.

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.
Now in Computational Geometry: Theory and Applications, Vol.~9, No.~4 (1998), pp.~237--246.

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),
Algorithmica (special issue for ESA'96), Vol. 21, No. 1 (May 1998), pp. 119--136.

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.

J. Klosowski, M. Held, J.S.B. Mitchell, H. Sowizral, K. Zikan:
``Efficient Collision Detection Using Bounding Volume Hierarchies of k-DOPs''
(Full paper submitted for journal publication)
Presented at SIGGRAPH'96: ``Real-Time Collision Detection for Motion Simulation within Complex Environments''
SIGGRAPH '96 Visual Proceedings; New Orleans, LA, USA, Aug 4-9, 1996.

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):
``Automatic Generation of Triangular Irregular Networks using Greedy Cuts''
Proc. Visualization'95, pp. 201-208, 1995.

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''
International Journal of Computational Geometry and Applications, Vol. 8, No. 3, pp.~343--363, June 1998
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.
International Journal of Computational Geometry and Applications, Vol. 7, No. 4, August 1997, pp. 317--347.

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.

J.S.B. Mitchell:
``On the Existence of Small Faces in Arrangements of Lines''
Manuscript, August, 1995.

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.

E. L. Wynters and J. S. B. Mitchell, ``Shortest Paths for a Two-Robot Rendez-Vous'',
Fifth Canadian Conference on Computational Geometry, Waterloo, August 5-9, 1993, pp. 216-221.

C. Zhu, G. Sundaram, J. Snoeyink, J. Mitchell:
``Generating Random Polygons with Given Vertices''
Computational Geometry: Theory and Applications, special issue on papers of CCCG 94, Vol. 6 (1996), No. 5, pp. 277--290.
Originally appeared with title ``Generating Random x-Monotone Polygons with Given Vertices'', in Proc. Sixth Canadian Conference on Computational Geometry, pp. 189-194, Saskatoon, Saskatchewan, August 2-6, 1994.
Based on a merge of a technical report, ``Generating Random Geometric Objects'', J. Mitchell and G. Sundaram, 1993, with a technical report of C. Zhu and J. Snoeyink, 1993.

Esther M. Arkin, Joseph S. B. Mitchell, and Christine D. Piatko,
Minimum-Link Watchman Tours, Information Processing Letters, Vol. 86, No. 4, May 2003, pp. 203-207.

E.M. Arkin, K. Kedem, J.S.B. Mitchell, J. Sprinzak, and M. Werman, Matching Points into Noise Regions: Combinatorial Bounds and Algorithms, in Proc. Second Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, CA, January 28-30, 1991, pp. 42-51. Full paper appears as ``Matching Points into Pairwise-Disjoint Noise Regions: Combinatorial Bounds and Algorithms'' in ORSA Journal on Computing Vol. 4, No. 4, 1992, pp. 375-386.

E. Arkin, J.S.B. Mitchell, and C. Piatko, ``Bicriteria Shortest Path Problems in the Plane'', Extended abstract appears in: Proc. Third Canadian Conference on Computational Geometry, Vancouver, B.C., August 5-10, 1991, pp. 153-156. See also the PhD thesis of Christine Piatko.

E.M. Arkin, P. Chew, D.P. Huttenlocher, K. Kedem, J.S.B. Mitchell, An Efficiently Computable Metric for Comparing Polygonal Shapes, Technical Report TR 89-1007, Department of Computer Science, Cornell University, May 1989. Appears in First ACM-SIAM Symposium on Discrete Algorithms (SODA'90), San Francisco, CA, January 22-24, 1990, pp. 129-137. Full paper appears in: IEEE Trans. on Pattern Analysis and Machine Intelligence, 13 (3), 1991, pp. 209-216.

Joe Mitchell (jsbm@ams.sunysb.edu)