Triangulation and Mesh Generation

• Delaunay Refinement for Piecewise Smooth Complexes.  pdf

  Siu-Wing Cheng, Tamal K.Dey, and Edgar A. Ramos.

  Discrete and Computational Geometry, 43 (2010), 121-166.

• Maintaining Deforming Surface Meshes. 

  Siu-Wing Cheng and Tamal K.Dey.

  Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms, 2008, 112-121.

• Delaunay Edge Flips in Dense Surface Triangulations. 

  Siu-Wing Cheng and Tamal K.Dey.

  Manuscript 2007.

  We temporarily retract this result because of a bug in Lemma 3.1. We are working on salvaging the other results in the manuscript without using Lemma 3.1.

• Sampling and Meshing a Surface with Guaranteed Topology and Geometry.  ps  pdf

  Siu-Wing Cheng, Tamal K. Dey, Edgar Ramos, and Tathagata Ray.

  SIAM Journal on Computing, 37 (2007), 1199-1227.

• A Practical Delaunay Meshing Algorithm for a Large Class of Domains.  pdf

  Siu-Wing Cheng, Tamal K.Dey, and Joshua A. Levine.

  Proceedings of the 16th International Meshing Roundtable, 2007, 477-494.

• Three-Dimensional Delaunay Mesh Generation.  ps  pdf

  Siu-Wing Cheng and Sheung-Hung Poon.

  Discrete and Computational Geometry, 36 (2006), 419-456.

• Anisotropic Surface Meshing. 

  Siu-Wing Cheng, Tamal K. Dey, Edgar A. Ramos, and Rephael Wenger.

  Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms, 2006, 202-211.

• Weighted Delaunay Refinement for Polyhedra with Small Angles.  ps  pdf

  Siu-Wing Cheng, Tamal K. Dey, and Tathagata Ray.

  Proceedings of 14th International Meshing Roundtable, 2005, 323-342.

• On the Sizes of Delaunay Meshes.  ps  pdf

  Siu-Wing Cheng.

  Computational Geometry: Theory and Applications, 33 (2006), 130-138.

• Quality Meshing for Polyhedra with Small Angles .  ps  pdf  

  Siu-Wing Cheng, Tamal K. Dey, Edgar Ramos, and Tathagata Ray.

  International Journal on Computational Geometry and Applications, 15 (2005), 421-461.

• Hierarchy of Surface Models and Irreducible Triangulation.  ps  pdf

  Siu-Wing Cheng, Tamal K. Dey and Sheung-Hung Poon.

  Computational Geometry Theory and Applications, 27 (2004), 135-150. 

• Quality Meshing with Weighted Delaunay Refinement.  ps  pdf

  Siu-Wing Cheng and Tamal K. Dey.

  SIAM Journal on Computing, 33 (2003), 69-93.

• Quadtree, Ray Shooting and Approximate Minimum Weight Steiner triangulation.   ps  pdf

  Siu-Wing Cheng and Kam-Hing Lee.

  Computational Geometry Theory and Applications, 23 (2002), 99-116.

• On β-skeleton as a subgraph of a minimum weight triangulation.  ps  pdf

  Siu-Wing Cheng and Yin-Feng Xu.

  Theoretical Computer Science A (Algorithms, automata, complexity and games), 262 (2001), 459-471. 

• LMT-Skeleton heuristics for several new classes of optimal triangulations. 

  Yang Dai, Naoki Katoh, and Siu-Wing Cheng. 

  Computational Geometry: Theory and Applications, 17 (2000), 51-68.

• Sliver Exudation.  ps  pdf

  Siu-Wing Cheng, Tamal K. Dey, Herbert Edelsbrunner, Michael A. Facello, and Shang-Hua Teng. 

  Journal of the Association for Computer Machinery, 47 (2000), 883-904.

• A study of the LMT-skeleton.

  Siu-Wing Cheng, Naoki Katoh, and Manabu Sugai.

  Proceedings of the 7th Annual International Symposium on Algorithms and Computation (ISAAC), 1996, 256-265.

• Triangulations intersect nicely. 

  Oswin Aichholzer, Franz Aurenhammer, Siu-Wing Cheng, Naoki Katoh, Gunter Rote, Michael Taschwer, and Yin-Feng Xu.

  Discrete & Computational Geometry, 16 (1996), 339-359.

Manifold Reconstruction

• Dimension Detection via Slivers.  pdf

  Siu-Wing Cheng and Man-Kwun Chiu.

  Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms, 2009, 1001-1010.

• Reconstructing Piecewise Curved Complexes.  pdf

  Siu-Wing Cheng and Yajun Wang.

  Manuscript, 2007.

• Provable Dimension Detection using Principal Component Analysis.  ps  pdf

  Siu-Wing Cheng, Yajun Wang, and Zhuangzhi Wu.

  International Journal of Computational Geometry and Applications, 18 (2008), 414-440.

  Preliminary version in Proceedings of the 21st Annual Symposium on Computational Geometry, 2005, 208-217.

• Manifold Reconstruction from Point Samples.  pdf

  Siu-Wing Cheng, Tamal K. Dey, and Edgar Ramos.

  Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, 2005, 1018-1027.

• Surface Reconstruction from Noisy Samples. 

  Siu-Wing Cheng and Sheung-Hung Poon. 

  Manuscript, 2004.

• Curve Reconstruction from Noisy Samples.  ps  pdf

  Siu-Wing Cheng, Stefan Funke, Mordecai Golin, Piyush Kumar, Sheung-Hung Poon, and Edgar Ramos. 

  Computational Geometry: Theory and Applications., 31 (2005), 63-100.

  Preliminary version in Proceedings of the 19th Annual ACM Symposium on Computational Geometry, 2003, 302-311.

Path Problems 

• Querying Approximate Shortest Paths in Anisotropic Regions.  ps  pdf

  Siu-Wing Cheng, Hyeon-Suk Na, Antoine Vigneron, and Yajun Wang.

  Proceedings of the 23rd Annual Symposium on Computational Geometry, 2007, 84-91.

• Approximate Shortest Paths in Anisotropic Regions.  ps  pdf

  Siu-Wing Cheng, Hyeon-Suk Na, Antoine Vigneron, and Yajun Wang.

  SIAM Journal on Computing, 38 (2008), 802-824.

Computer-Aided Design and Manufacturing 

• Casting an Object with a Core.  ps pdf

  Hee-Kap Ahn, Sang Won Bae, Siu-Wing Cheng, Sang Wong Bae, and Kyung-Yong Chwa.

  Algorithmica, 54 (2009), 72-88.

• Casting with Skewed Ejection Direction.  ps  pdf

  Hee-Kap Ahn, Siu-Wing Cheng, and Otfried Cheong.

  Algorithmica, 44 (2006), 325-342.

• The Reflex-Free Hull.  pdf

  Hee-Kap Ahn, Siu-Wing Cheng, Otfried Cheong, and Jack Snoeyink.

  International Journal on Computational Geometry and Applications, 14 (2004), 453-474.

• Separating an object from its cast.  ps  pdf

  Hee-Kap Ahn, Mark de Berg, Prosenjit Bose, Siu-Wing Cheng, Dan Halperin, Jiri Matousek, and Otfried Schwarzkopf. 

  Computer Aided Design, 34 (2002), 547-559. 

• Approximation algorithms for multiple-tool milling.  ps  pdf

  Sunil Arya, Siu-Wing Cheng, and David Mount. 

  International Journal on Computational Geometry and Applications, 11 (2001), 339-372. 

• Design and analysis of planar shape deformation.

  Siu-Wing Cheng, Herbert Edelsbrunner, Ping Fu and Patrick Lam.

  Computational Geometry: Theory and Applications, 19 (2001), 205-218.

Dynamic Algorithms and Data Structures 

• Indexing Uncertain Data.    pdf  

  Pankaj K. Agarwal, Siu-Wing Cheng, Yufei Tao, and Ke Yi.

  Proceedings of the Symposium on Principles of Database Systems, 2009, 137-146.

• Hierarchical Decompositions and Circular Ray Shooting in Simple Polygons.   ps  pdf  

  Siu-Wing Cheng, Otfried Cheong, Hazel Everett, and Rene van Oostrum.

  Discrete & Computational Geometry, 32 (2004), 401-415.

• Motorcycle Graphs and Straight Skeletons.   ps  pdf  

  Siu-Wing Cheng and Antoine Vigneron

  Algorithmica, 47 (2007), 159-182. 

• Efficient Expected-Case Algorithms for Planar Point Location.

  Sunil Arya, Siu-Wing Cheng, David M. Mount, and H. Ramesh.

  Proceedings of the 7th Scandinavian Workshop on Algorithm Theory, 2000, 353-366.

• Isomorphism testing and display of symmetries for dynamic trees.

  Siu-Wing Cheng and Moon-Pun Ng. 

  Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms, 1996, 202-211.

• Algorithms for ray-shooting and intersection searching. 

  Siu-Wing Cheng and Ravi Janardan. 

  Journal of Algorithms, 13 (1992), 670-692.

• New results on dynamic planar point location.

  Siu-Wing Cheng and Ravi Janardan. 

  SIAM Journal on Computing, 21 (1992), 972-999. 

• Efficient maintenance of the union of intervals on a line, with applications.

  Siu-Wing Cheng and Ravi Janardan. 

  Journal of Algorithms, 12 (1991) 57-74. 

• Efficient dynamic algorithms for some geometric intersection problems.

  Siu-Wing Cheng and Ravi Janardan.

  Information Processing Letters, 36 (1990), 251-258.

Rectilinear Steiner Trees 

• The Steiner tree problem for terminals on the boundary of a rectilinear polygon. 

  Siu-Wing Cheng.

  Theoretical Computer Science A (Algorithms, automata, complexity and games), 237 (2000), 213-238.

• A fast algorithm for computing optimal rectilinear Steiner tree for extremal point sets. 

  Siu-Wing Cheng and Chi-Keung Tang. 

  Proceedings of the 6th Annual International Symposium on Algorithms and Computation (ISAAC), 1995, 322-331.

• Optimal rectilinear Steiner tree for extremal point sets.

  Siu-Wing Cheng, Andrew Lim, and Ching-Ting Wu.

  Proceedings of the 4th Annual Symposium on Algorithms and Computation (ISAAC), 1993, 523-532.

• Performance Oriented Rectilinear Steiner Trees. 

  Andrew Lim, Siu-Wing Cheng, and Ching-Ting Wu. 

  Proceedings of the 30th Design Automation Conference, 1993, 171-176.

Miscellaneous 

• Competitive Facility Location: The Voronoi Game.  ps  pdf

  Hee-Kap Ahn, Siu-Wing Cheng, Otfried Cheong, Mordecai Golin, and Rene van Oostrum. 

  Theoretical Computer Science A (Algorithms, automata, complexity and games), 310 (2004), 457-467.

• Minimum dominating sets of intervals on lines. 

  Siu-Wing Cheng, Michael Kaminski, and Shmuel Zaks. 

  Algorithmica, 20 (1998), 294-308.

• Widest empty L-shaped corridor. 

  Siu-Wing Cheng.

  Information Processing Letters, 58 (1996), 277-283.

• Modifications of competitive group testing. 

  Ding-Zhu Du, Guo-Liang Xue, Shang-Zhi Sun, and Siu-Wing Cheng. 

  SIAM Journal on Computing, 23 (1994), 82-96.

• The role of long and short paths in circuit performance optimization.

  Siu-Wing Cheng, Hsi-Chuan Chen, David H.C. Du, and Andrew Lim.

  IEEE Transactions on Computer-Aided Design, 13 (1994), 857-864.

• Optimal joining of compacted cells. 

  Andrew Lim, Siu-Wing Cheng, and Sartaj Sahni. 

  IEEE Transactions on Computers, 42 (1993), 597-607. 

• Single jog minimum area joining of compacted cells.

  Andrew Lim, Yeow-Meng Chee, and Siu-Wing Cheng.

  Information Processing Letters, 47 (1993), 167-172.

• Circuit enhancement by long false path elimination. 

  Hsi-Chuan Chen, David H.C. Du, and Siu-Wing Cheng.

  Proceedings of the 29th Design Automation Conference, 1992, 249-252.

• A path sensitization approach to area optimization. 

  Hsi-Chuan Chen, Siu-Wing Cheng, Yaun-chung Hsu, and David H.C. Du. 

  Proceedings of IEEE International Conference on Computer Design: VLSI in Computers and Processors, 1993, 73-76.

• Efficient distributed algorithms for single-source shortest paths and related problems on plane networks.

  Ravi Janardan and Siu-Wing Cheng. 

  Mathematical Systems Theory, 25 (1992), 93-122.

Book Chapters 

• Planar straight line graphs. 

  Siu-Wing Cheng. 

  Handbook of Data Structures and Applications, (eds. Dinesh P. Mehta and Sartaj Sahni).

  CRC, 2005.

• Exact Steiner tree in graphs and grid graphs. 

  Siu-Wing Cheng.

  Advances in Steiner Trees, (eds. Ding-Zhu Du, J. MacGregor Smith and J.H. Rubinstein).

  Kluwer Academic Publishers, 2000, 137-162.