Book

Siu-Wing Cheng, Tamal Krishna Dey, and Jonathan Richard Shewchuk.  Delaunay Mesh Generation.  CRC Press, 2012.

Refereed Conference Articles

1.          Siu-Wing Cheng and Jiongxin Jin.  Approximate Shortest Descending Path.  Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2013, 144-155.

2.          Hee-Kap Ahn, Siu-Wing Cheng, Hyuk Jun Kweon, and Juyoung Yon.  Overlap of Convex Polytopes under Rigid Motion.  Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), 2012.

3.          Siu-Wing Cheng, Jiongxin Jin, and Man-Kit Lau.  A Fast and Simple Surface Reconstruction Algorithm.  Proceedings of the 28th Annual Symposium on Computational Geometry (SOCG), 2012, 69-78.

4.          Siu-Wing Cheng and Jiongxin Jin.  Edge Flips and Deforming Surface Meshes.   Proceedings of the 27th Annual Symposium on Computational Geometry (SOCG), 2011, 331-340.

5.          Hee-Kap Ahn, Siu-Wing Cheng, and Iris Reinbacher.  Maximum Overlap of Convex Polytopes under Translation.  Proceedings of the 21st International Symposium on Algorithms and Computation (ISAAC), 2010, 97-108.

6.          Siu-Wing Cheng, Jiongxin Jin, Antoine Vigneron, and Yajun Wang.  Approximate Homotopic Shortest Paths in Anisotropic Regions.  Proceedings of the 21st International Symposium on Algorithms and Computation (ISAAC), 2010, 109-121.

7.          Siu-Wing Cheng, Christian Knauer, Stefan Langerman, and Michiel Smid.  Approximating the Average Stretch Factor of Geometric Graphs.  Proceedings of the 21st International Symposium on Algorithms and Computation (ISAAC), 2010, 37-48.

8.          Pankaj K. Agarwal, Siu-Wing Cheng, Yufei Tao, and Ke Yi.  Indexing Uncertain Data.  Proceedings of the Symposium on Principles of Database Systems (PODS), 2009, 137-146.

9.          Siu-Wing Cheng and Man-Kwun Chiu.  Dimension Detection via Slivers.  Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2009, 1001-1010.

10.     Siu-Wing Cheng and Tamal K. Dey.  Maintaining Deforming Surface Meshes.   Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2008, 112-121.

11.     Siu-Wing Cheng, Tamal K. Dey, and Joshua A. Levine.  A Practical Delaunay Meshing Algorithm for a Large Class of Domains.  Proceedings of the 16th International Meshing Roundtable (IMR), 2007, 477-494.

12.     Siu-Wing Cheng, Hyeon-Suk Na, Antoine Vigneron, and Yajun Wang.  Querying Approximate Shortest Paths in Anisotropic Regions.  Proceedings of the 23rd Annual Symposium on Computational Geometry (SOCG), 2007, 84-91.

13.     Siu-Wing Cheng, Hyeon-Suk Na, Antoine Vigneron, and Yajun Wang.  Approximate Shortest Paths in Anisotropic Regions.  Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2007, 766-774.

14.     Siu-Wing Cheng, Tamal K. Dey, and Edgar A. Ramos.  Delaunay Refinement for Piecewise Smooth Complexes.  Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2007, 1096-1105.

15.     Siu-Wing Cheng, Tamal K. Dey, Edgar A. Ramos, and Raphael Wenger.  Anisotropic Surface Meshing.  Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2006, 202-211.

16.     Hee-Kap Ahn, Sang Won Bae, Siu-Wing Cheng, and Kyung-Yong Chwa.  Casting an Object with a Core.  Proceedings of the 16th International Symposium on Algorithms and Computation (ISAAC) 2005, 40-49.

17.     Siu-Wing Cheng, Tamal K. Dey, and Tathagata Ray.  Weighted Delaunay Refinement for Polyhedra with Small Angles.  Proceedings of the 14th International Meshing Roundtable (IMR) 2005, 323-342.

18.     Siu-Wing Cheng, Yajun Wang, and Zhuangzhi Wu.  Provable Dimension Detection using Principal Component Analysis.  Proceedings of the 21th Annual Symposium on Computational Geometry (SOCG), 2005, 208-217.

19.     Siu-Wing Cheng, Tamal K. Dey, and Edgar A. Ramos.  Manifold Reconstruction from Point Samples.  Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) 2005, 1018-1027.

20.     Siu-Wing Cheng, Tamal K. Dey, Edgar A. Ramos, and Tathagata Ray.  Sampling and Meshing a Surface with Guaranteed Topology and Geometry.  Proceedings of the 20th Annual Symposium on Computational Geometry (SOCG), 2004, 280-289.

21.     Siu-Wing Cheng, Tamal K. Dey, Edgar A. Ramos, and Tathagata Ray.  Quality Meshing for Polyhedra with Small Angles.  Proceedings of the 20th Annual Symposium on Computational Geometry (SOCG), 2004, 290-299.

22.     Siu-Wing Cheng, Stefan Funke, Mordecai Golin, Piyush Kumar, Sheung-Hung Poon, and Edgar A. Ramos.  Curve Reconstruction from Noisy Samples.  Proceedings of the 19th Annual Symposium on Computational Geometry (SOCG), 2003, 302-311.

23.     Siu-Wing Cheng and Sheung-Hung Poon.  Graded Conforming Delaunay Tetrahedralization with Bounded Radius-Edge Ratio.  Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2003, 295-304.

24.     Siu-Wing Cheng, Tamal K. Dey and Sheung-Hung Poon.  Hierarchy of Surface Models and Irreducible Triangulation.  Proceedings of the 13th International Symposium on Algorithms and Computation (ISAAC), 2002, 286-295.

25.     Siu-Wing Cheng and Antoine Vigneron.  Motorcycle Graphs and Straight Skeletons.  Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2002, 156-165.

26.     Siu-Wing Cheng and Tamal K. Dey.  Quality Meshing with Weighted Delaunay refinement.  Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2002, 137-146.

27.     Hee-Kap Ahn, Siu-Wing Cheng, Otfried Cheong, Mordecai Golin, and Rene van Oostrum.  Competitive Facility Location along a Highway.  Proceedings of the 7th Annual International Computing and Combinatorics Conference (COCOON), 2001, 231-246.

28.     Sunil Arya, Siu-Wing Cheng, David M. Mount, and Hariharan Ramesh.  Efficient Expected-Case Algorithms for Planar Point Location.  Proceedings of the 7th Scandinavian Workshop on Algorithm Theory (SWAT), 2000, 353-366.

29.     Siu-Wing Cheng, Otfried Cheong, Hazel Everett, and Rene van Oostrum.  Hierarchical Vertical Decompositions, Ray Shooting, and Circular Arc Queries in Simple Polygons.  Proceedings of th15th Annual Symposium on Computational e Geometry (SOCG), 1999, 227-236.

30.     Siu-Wing Cheng, Tamal K. Dey, Herbert Edelsbrunner, Michael A. Facello, and Shang-Hua Teng.  Sliver Exudation.  Proceedings of the 15th Annual Symposium on Computational Geometry (SOCG), 1999, 1-13.

31.     Siu-Wing Cheng and Kam-Hing Lee.  Quadtree decomposition, Steiner triangulation, and Ray Shooting.  Proceedings of the 9th Annual International Symposium on Algorithms and Computation (ISAAC), 1998, 367-376.

32.     Hee-Kap Ahn, Siu-Wing Cheng, and Otfried Cheong.  Casting with Skewed Ejection Direction.  Proceedings of the 9th Annual International Symposium on Algorithms and Computation (ISAAC), 1998, 139-148.

33.     Sunil Arya, Siu-Wing Cheng, and David Mount.  Approximation Algorithms for Multiple-Tool Milling.  Proceedings of the 14th Annual Symposium on Computational Geometry (SOCG), 1998, 297-306.

34.     Siu-Wing Cheng, Herbert Edelsbrunner, Ping Fu, and Ka-Po Lam.  Design and Analysis of Planar Shape Deformation.  Proceedings of the 14th Annual Symposium on Computational Geometry (SOCG), 1998, 29-38.

35.     Hee-Kap Ahn, Mark de Berg, Prosenjit Bose, Siu-Wing Cheng, Dan Halperin, Jiri Matousek, and Otfried Schwarzkopf.  Separating an Object from its Cast.  Proceedings of the 13th Annual Symposium on Computational Geometry (SOCG), 1997, 221-230.

36.     Siu-Wing Cheng, Naoki Katoh, and Manabu Sugai.  A Study of the LMT-Skeleton.  Proceedings of the 7th Annual International Symposium on Algorithms and Computation (ISAAC), 1996, 256-265.

37.     Siu-Wing Cheng and Yin-Feng Xu.  Approaching the Largest †¦ﮣSkeleton within a MinimumWeight Triangulation.  Proceedings of 12th Annual Symposium on Computational Geometry (SOCG), 1996, 196-203.

38.     Siu-Wing Cheng and Moon-Pun Ng.  Isomorphism Testing and Display of Symmetries for Dynamic Trees.  Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 1996, 202-211.

39.     Siu-Wing Cheng and Chi-Keung Tang.  A Fast Algorithm for Computing Optimal Rectilinear Steiner Tree for Extremal Point Sets.  Proceedings of the 6th Annual International Symposium on Algorithms and Computation (ISAAC), 1995, 322-331.

40.     Siu-Wing Cheng and Yin-Feng Xu.  Constrained Independence System and Triangulation of Planar Point Sets.  Proceedings of the First Annual International Computing and Combinatorics Conference (COCOON), 1995, 41-50.

41.     Siu-Wing Cheng, Michael Kaminski and Shmuel Zaks.  Minimum Dominating Sets of Intervals on Lines.  Proceedings of the First Annual International Computing and Combinatorics Conference (COCOON), 1995, 520-529.

42.     Siu-Wing Cheng, Andrew Lim, and Ching-Ting Wu.  Optimal Rectilinear Steiner Tree for Extremal Point Sets.  Proceedings of the 4th Annual Symposium on Algorithms and Computation (ISAAC), 1993, 523-532.

43.     Hsi-Chuan Chen, Siu-Wing Cheng, Yaun-Chung Hsu, and David H.C. Du.  A Path Sensitization Approach to Area Optimization.  Proceedings of IEEE International Conference on Computer Design: VLSI in Computers and Processors, 1993, 73-76.

44.     Andrew Lim, Siu-Wing Cheng, and Ching-Ting Wu.  Performance Oriented Rectilinear Steiner Trees.  Proceedings of the 30th Design Automation Conference (DAC), 1993, 171-176.

45.     Hsi-Chuan Chen, David H.C. Du, and Siu-Wing Cheng.  Circuit Enhancement by Long False Path Elimination.  Proceedings of the 29th Design Automation Conference (DAC), 1992, 249-252.

46.     Siu-Wing Cheng, Hsi-Chuan Chen, David H.C. Du, and Andrew Lim.  The Role of Long and Short Paths in Circuit Performance Optimization.  Proceedings of the 29th Design Automation Conference (DAC), 1992, 543-548.

47.     Andrew Lim, Siu-Wing Cheng, and Sartaj Sahni.  Optimal Joining of Compacted Cells.  Proceedings of the 1992 Brown/MIT Conference on Advanced Research in VLSI and Parallel Systems, 99-112.

48.     Siu-Wing Cheng and Ravi Janardan.  Space-Efficient Ray-Shooting and Intersection Searching: Algorithms, Dynamization, and Applications.  Proceedings of the 2nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 1991, 7-16.

49.     Siu-Wing Cheng and Ravi Janardan. Efficient Maintenance of the Union of Intervals on a Line, with Applications.  Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 1990, 74-83.

50.     Siu-Wing Cheng and Ravi Janardan.  New results on Dynamic Planar Point Location.  Proceedings of the 31st Annual IEEE Symposium on Foundations of Computer Science (FOCS), 1990, 96-105.

Refereed Journal Articles

1.        Siu-Wing Cheng and Chi-Kit Lam.  Shape Matching under Rigid Motion.  Accepted to Computational Geometry: Theory and Applications.

2.        Hee-Kap Ahn, Siu-Wing Cheng, and Iris Reinbacher.  Maximum Overlap of Convex Polytopes under Translation. Accepted to Computational Geometry: Theory and Applications.

3.        Siu-Wing Cheng, Jiongxin Jin, Antoine Vigneron, and Yajun Wang.  Approximate Shortest Homotopic Paths in Weighted Regions.  International Journal of Computational Geometry and Applications, 22 (2012), 83-102.

4.        Pankaj K. Agarwal, Siu-Wing Cheng, and Ke Yi.  Range Searching on Uncertain Data.  ACM Transactions on Algorithms, 8 (2012), Article 43, 17 pages.

5.        Siu-Wing Cheng, Hyeon-Suk Na, Antoine Vigneron, and Yajun Wang.  Querying Approximate Shortest Paths in Anisotropic Regions.  SIAM Journal on Computing, 39 (2010), 1888-1918.

6.        Siu-Wing Cheng, Tamal K. Dey, and Edgar A. Ramos.  Delaunay Refinement for Piecewise Smooth Complexes.  Discrete and Computational Geometry, 43 (2010), 121-166.

7.        Hee-Kap Ahn, Sang Won Bae, Siu-Wing Cheng, and Kyung-Yong Chwa.  Casting an Object with a Core.  Algorithmica, 54 (2009), 72-88.

8.        Siu-Wing Cheng, Yajun Wang, and Zhuangzhi Wu.  Provable Dimension Detection using Principal Component Analysis.  International Journal of Computational Geometry and Applications, 18 (2008), 415-440.

9.        Siu-Wing Cheng, Hyeon-Suk Na, Antoine Vigneron, and Yajun Wang.  Approximate Shortest Paths in Anisotropic Regions.  SIAM Journal on Computing, 38 (2008), 802-824.

10.   Siu-Wing Cheng, Tamal K. Dey, Edgar A. Ramos, and Tathagata Ray.  Sampling and Meshing a Surface with Guaranteed Topology and Geometry.  SIAM Journal on Computing, 37 (2007), 1199-1227.

11.   Siu-Wing Cheng and Antoine Vigneron.  Motorcycle Graphs and Straight Skeletons.  Algorithmica, 47 (2007), 159-182.

12.   Hee-Kap Ahn, Siu-Wing Cheng, and Otfried Cheong.  Casting with Skewed Ejection Direction.   Algorithmica, 44 (2006), 325-342.

13.   Siu-Wing Cheng.  On the Sizes of Delaunay Meshes.  Computational Geometry: Theory and Applications, 33 (2006), 130-138.

14.   Siu-Wing Cheng and Sheung-Hung Poon.  Three-Dimensional Delaunay Mesh Generation.  Discrete and Computational Geometry, 36 (2006), 419-456.

15.   Siu-Wing Cheng, Stefan Funke, Mordecai Golin, Piyush Kumar, Sheung-Hung Poon, and Edgar A. Ramos.  Curve Reconstruction from Noisy Samples.  Computational Geometry: Theory and Applications, 31 (2005), 63-100 (Special issue of SOCG 2003).

16.   Siu-Wing Cheng, Tamal K. Dey, Edgar A. Ramos, and Tathagata Ray.  Quality Meshing for Polyhedra with Small Angles.  International Journal of Computational Geometry and Applications, 15 (2005), 421-461 (Special issue of SOCG 2004).

17.   Hee-Kap Ahn, Siu-Wing Cheng, Otfried Cheong, and Jack Snoeyink.  The Reflex-Free Hull.  International Journal on Computational Geometry and Applications, 14 (2004), 453-474.

18.   Siu-Wing Cheng, Otfried Cheong, Hazel Everett, and Rene van Oostrum.  Hierarchical Decompositions and Circular Ray Shooting in Simple Polygons.  Discrete and Computational Geometry, 32 (2004), 401-415.

19.   Hee-Kap Ahn, Siu-Wing Cheng, Otfried Cheong, Mordecai Golin, and Rene van Oostrum.  Competitive Facility Location: The Voronoi Game.  Theoretical Computer Science A (Algorithms, automata, complexity and games), 310 (2004), 457-467.

20.   Siu-Wing Cheng, Tamal K. Dey, and Sheung-Hung Poon.  Hierarchy of Surface Models and Irreducible Triangulation.  Computational Geometry: Theory and Applications, 27 (2004), 135-150.

21.   Siu-Wing Cheng and Tamal K. Dey.  Quality Meshing with Weighted Delaunay Refinement.  SIAM Journal on Computing, 33 (2003), 69-93.

22.   Siu-Wing Cheng and Kam-Hing Lee.  Quadtree, Ray Shooting and Approximate Minimum Weight Steiner triangulation.  Computational Geometry: Theory and Applications, 23 (2002), 99-116.

23.   Hee-Kap Ahn, Mark de Berg, Prosenjit Bose, Siu-Wing Cheng, Dan Halperin, Jiri Matousek, and Otfried Schwarzkopf.  Separating an Object from its Cast.  Computer Aided Design, 34 (2002), 547-559.

24.   Sunil Arya, Siu-Wing Cheng, and David Mount.  Approximation Algorithms for Multiple-Tool Milling.  International Journal of Computational Geometry and Applications, 11 (2001), 339-372 (Special issue of SOCG 1998).

25.   Siu-Wing Cheng, Herbert Edelsbrunner, Ping Fu, and Ka-Po Lam.  Design and Analysis of Planar Shape Deformation.  Computational Geometry: Theory and Applications, 19 (2001), 205-218.

26.   Siu-Wing Cheng and Yin-Feng Xu.  On Skeleton as a Subgraph of a Minimum Weight Triangulation.  Theoretical Computer Science A (Algorithms, automata, complexity and games), 262 (2001), 459-471.

27.   Yang Dai, Naoki Katoh, and Siu-Wing Cheng.  LMT-Skeleton Heuristics for several New Classes of Optimal Triangulations.  Computational Geometry: Theory and Applications, 17 (2000), 51-68.

28.   Siu-Wing Cheng, Tamal K. Dey, Herbert Edelsbrunner, Michael A. Facello, and Shang-Hua Teng.   Sliver Exudation.  Journal of the Association for Computer Machinery, 47 (2000), 883-904.

29.   Siu-Wing Cheng.  The Steiner Tree Problem for Terminals on the Boundary of a Rectilinear Polygon.  Theoretical Computer Science A (Algorithms, automata, complexity and games), 237 (2000), 213-238.

30.   Siu-Wing Cheng, Michael Kaminski, and Shmuel Zaks.  Minimum Dominating Sets of Intervals on Lines.  Algorithmica, 20 (1998), 294-308.

31.   Oswin Aichholzer, Franz Aurenhammer, Siu-Wing Cheng, Naoki Katoh, Gunter Rote, Michael Taschwer, and Yin-Feng Xu.  Triangulations Intersect Nicely.  Discrete and Computational Geometry, 16 (1996), 339-359.

32.   Siu-Wing Cheng.  Widest Empty L-shaped Corridor.  Information Processing Letters, 58 (1996), 277-283.

33.   Ding-Zhu Du, Guo-Liang Xue, Shang-Zhi Sun, and Siu-Wing Cheng.  Modifications of Competitive Group Testing.  SIAM Journal on Computing, 23 (1994), 82-96.

34.   Siu-Wing Cheng, Hsi-Chuan Chen, David H.C. Du, and Andrew Lim.  The Role of Long and Short Paths in Circuit Performance Optimization.  IEEE Transactions on Computer-Aided Design, 13 (1994), 857-864.

35.   Andrew Lim, Siu-Wing Cheng, and Sartaj Sahni.  Optimal Joining of Compacted Cells.  IEEE Transactions on Computers, 42 (1993), 597-607.

36.   Andrew Lim, Siu-Wing Cheng, and Ching-Ting Wu.  Performance Oriented Rectilinear Steiner Trees.  Eletrik, 1 (1993), 137-152.

37.   Andrew Lim, Yeow-Meng Chee, and Siu-Wing Cheng.  Single Jog Minimum Area Joining of Compacted Cells.  Information Processing Letters, 47 (1993), 167-172.

38.   Ravi Janardan and Siu-Wing Cheng.  Efficient Distributed Algorithms for Single-Source Shortest Paths and Related Problems on Plane Networks.  Mathematical Systems Theory, 25 (1992), 93-122.

39.   Siu-Wing Cheng and Ravi Janardan.  Algorithms for Ray-Shooting and Intersection Searching.   Journal of Algorithms, 13 (1992), 670-692.

40.   Siu-Wing Cheng and Ravi Janardan.  New Results on Dynamic Planar Point Location.  SIAM Journal on Computing, 21 (1992), 972-999.

41.   Siu-Wing Cheng and Ravi Janardan.  Efficient Maintenance of the Union of Intervals on a Line, with Applications.  Journal of Algorithms, 12 (1991) 57-74.

42.   Siu-Wing Cheng and Ravi Janardan.  Efficient Dynamic Algorithms for some Geometric Intersection Problems.  Information Processing Letters, 36 (1990), 251-258.