Siu-Wing Cheng Professor Department of Computer Science and Engineering HKUST, Clear Water Bay Hong Kong Email: scheng@cse.ust.hk Tel: 852 23586973 Fax: 852 23581477

 

I enjoy doing research in algorithms, data structures, and computational geometry.  I have written a book, Delaunay Mesh Generation, with Tamal Dey and Jonathan Shewchuk.  It is a thorough guide to Delaunay triangulation and mesh generation by  Delaunay refinement.

 

 

 

Selected Professional Activities  (full list)

ACM Distinguished Member for scientific contributions to computing. Editorial board member of Computational Geometry: Theory and Applications. Associate editor of International Journal of Computational Geometry and Applications. Editorial board member of Journal of Computational Geometry. Program co-chair of the 30th Annual Symposium on Computational Geometry, June 8-11, 2014, Kyoto, Japan. Program co-chair of the 24th International Symposium on Algorithms and Computation, December 16-18, 2014, Hong Kong. Some recent PC membership: SoCG18, SODA16, SWAT14, SoCG14, ISAAC13, WADS13, SoCG13, ISAAC12, ICALP12. Advisory committee member of the International Symposium on Algorithms and Computation (ISAAC). Chair of the Asian Association for Algorithms and Computation (AAAC).

 

Selected University Service

Associate Dean (Undergraduate Studies) of the School of Engineering, HKUST, January 2016 - December 2019. Acting Head of the Department of Computer Science and Engineering, HKUST, August 2013 - December 2014. Associate Head of the Department of Computer Science and Engineering, HKUST, September 2007 - August 2011.

 

       Selected Publications  (full list)

        Self-Improving Algorithms

• Siu-Wing Cheng, Man-Kwun Chiu, Kai Jin, and Man Ting Wong.  A Generalization of Self-Improving Algorithms.  Proceedings of the 36th International Symposium on Computational Geometry, 2020.
• Siu-Wing Cheng, Kai Jin, and Lie Yan.  Extensions of Self-Improving Sorters.  Algorithmica, 82 (2020), 88-106.

        Max-Min Fair Allocation

• Siu-Wing Cheng and Yuchen Mao.  Restricted Max-Min Allocation: Approximation and Integrality Gap.  Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019, 38:1-38:13.
• Siu-Wing Cheng and Yuchen Mao.  Restricted Max-Min Fair Allocation.  Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018, 37:1-13.

        Point Location

• Siu-Wing Cheng and Man-Kit Lau.  Dynamic Distribution-Sensitive Point Location.   Proceedings of the 36th International Conference on Computational Geometry (SOCG), 2020.
• Siu-Wing Cheng and Man-Kit Lau.  Adaptive Planar Point Location.   Proceedings of the International Conference on Computational Geometry (SOCG), 2017, 30:1-15.  Journal version accepted by SIAM Journal on Computing.
• Siu-Wing Cheng and Man-Kit Lau.  Adaptive Point Location in Planar Convex Subdivisions.  International Journal of Computational Geometry and Applications, 27 (2017), 3-12, special issue for the Proceedings of the 26th Internatinoal Symposium on Algorithms and Computation (ISAAC), 2015.
• Siu-Wing Cheng and Ravi Janardan.  New Results on Dynamic Planar Point Location.  SIAM Journal on Computing, 21 (1992), 972-999.

        Approximate Shortest Paths

• Siu-Wing Cheng, Man-Kwun Chiu, Jiongxin Jin, and Antoine Vigneron.  Navigating Weighted Regions with Scattered Skinny Tetrahedra.  International Journal of Computational Geometry and Applications, 27 (2017), 13-32, special issue for Proceedings of the 26th International Symposium on Algorithms and Computation (ISAAC), 2015.
• Siu-Wing Cheng, Jiongxin Jin, and Antoine Vigneron. Triangulation Refinement and Approximate Shortest Paths in Weighted Regions. Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, 2015, 1626-1640.
• Siu-Wing Cheng and Jiongxin Jin. Shortest Paths on Polyhedral Surfaces and Terrains. Proceedings of the 46th Annual ACM Sympoisum on Theory of Computing, 2014, 373-382.
• Siu-Wing Cheng and Jiongxin Jin.  Approximate Shortest Descending Paths.  SIAM Journal on Computing, 43 (2014), 410-428.
• 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.
• 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.
• 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.

        Mesh Generation

• Siu-Wing Cheng and Jionxin Jin.  Edge Flips in Surface Meshes.  Discrete and Computational Geometry, 54 (2015), 110-151.
• Siu-Wing Cheng and Jiongxin Jin. Deforming Surface Meshes.  New Challenges in Grid Generation and Adaptivity for Scientific Computing, SEMA SIMAI Springer Series 5, edited by Simona Perotto and Luca Formaggia, pages 69-90, 2015.
• Siu-Wing Cheng, Tamal K. Dey, and Edgar A. Ramos.  Delaunay Refinement for Piecewise Smooth Complexes.  Discrete and Computational Geometry, 43 (2010), 121-166.
• 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, 2007, 477-494.
• 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.
• Siu-Wing Cheng and Sheung-Hung Poon.  Three-Dimensional Delaunay Mesh Generation.  Discrete and Computational Geometry, 36 (2006), 419-456.
• 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, 2006, 202-211.
• Siu-Wing Cheng, Tamal K. Dey, and Tathagata Ray.  Weighted Delaunay Refinement for Polyhedra with Small Angles.  Proceedings of the 14th International Meshing Roundtable, 2005, 323-342.
• Siu-Wing Cheng and Tamal K. Dey.  Quality Meshing with Weighted Delaunay Refinement.  SIAM Journal on Computing, 33 (2003), 69-93.
• 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.

        Reconstruction of  Surfaces and Manifolds

• Siu-Wing Cheng and Man-Kwun Chiu.  Implicit Manifold Reconstruction.  Discrete and Computational Geometry, 62 (2019), 700-742.
• Siu-Wing Cheng and Man-Kit Lau.  Denoising a Point Cloud for Surface Reconstruction.   arXiv:1704.04028.   Missing images from the paper in the archive can be found here.  The code can be downloaded from the project page.
• Siu-Wing Cheng, Jiongxin Jin, and Man-Kit Lau.  A Fast and Simple Surface Reconstruction Algorithm.  ACM Transactions on Algorithms, volume 13, issue 2, March 2017, article no. 27.
• Siu-Wing Cheng and Man-Kwun Chiu.  Tangent Estimation from Point Samples.  Discrete and Computational Geometry, 56 (2016), 505-557.
• Siu-Wing Cheng and Man-Kwun Chiu. Implicit Manifold Reconstruction. Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, 2014, 161-173.
• Siu-Wing Cheng and Man-Kwun Chiu.  Dimension Detection via Slivers.  Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms, 2009, 1001-1010.
• 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.
• 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, 2005, 1018-1027.
• 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).

Shape Matching

• Juyoung Yon, Siu-Wing Cheng, Otfried Cheong, and Antoine Vigneron.  Finding Largest Common Point Sets.  International Journal of Computational Geometry and Applications, 27 (2017), 177-185.
• Juyoung Yon, Sang Won Bae, Siu-Wing Cheng, Otfried Cheong, and Bryan T. Wilkinson.  Approximating Convex Shapes with respect to Symmetric Difference under Homotheties.  Proceedings of the International Symposium on Computational Geometry (SOCG), 2016, 63:1-15..
• Hee-Kap Ahn, Siu-Wing Cheng, Hyuk Jun Kweon, and Juyoung Yon.  Overlap of Convex Polytopes under Rigid Motion, Computational Geometry: Theory and Applications, 47 (2014), 15-24.
• Siu-Wing Cheng and Chi-Kit Lam.  Shape Matching under Rigid Motion.  Computational Geometry: Theory and Applications, 46 (2013), 591-603.
• Hee-Kap Ahn, Siu-Wing Cheng, and Iris Reinbacher.  Maximum Overlap of Convex Polytopes under Translation. Computational Geometry: Theory and Applications, 46 (2013), 552-565.

Other Topics

• Siu-Wing Cheng, Yuya Higashikawa, Naoki Katoh, and Adnan Slijoka.  Characterizing Minimal Rigidity of Square-Grid Frameworks with Holes.  Proceedings of the 10th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, 2017, 93-102.
• Siu-Wing Cheng, Liam Mencel, and Antoine Vigneron. A Faster Algorithm for Computing Straight Skeletons. ACM Transactions on Algorithms, volume 12, issue 3, article 44, May, 2016.
• Ge Luo, Ke Yi, Siu-Wing Cheng, Zhenguo Li, Wei Fan, Cheng He, and Yadong Mu. Piecewise Linear Approximation of Streaming Time Series Data with Max-error Guarantees. Proceedings of the 31st IEEE International Conference on Data Engineering, 2015, 173-184.
• Yuya Higashikawa, John Augustine, Siu-Wing Cheng, Mordecai J. Golin, Naoki Katoh, Guanqun Ni, Bing Su, and Yinfeng Xu.  Minimax Regret 1-Sink Location Problem in Dynamic Path Networks.  Theoretical Computer Science, 588 (2015), 24-36.
• Pankaj K. Agarwal, Siu-Wing Cheng, and Ke Yi.  Range Searching on Uncertain Data.  ACM Transactions on Algorithms, 8 (2012), Article 43, 17 pages.
• Siu-Wing Cheng and Antoine Vigneron.  Motorcycle Graphs and Straight Skeletons.  Algorithmica, 47 (2007), 159-182.