Siu-Wing Cheng

Professor
Department of Computer Science and Engineering
HKUST, Clear Wate Bay
Hong Kong
Emai: scheng@cse.ust.hk

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

ACM Distinguished Member for scientific contributions to computing.
Editorial board members of Computing in Geometry and Topology and Computational Geometry: Theory and Applications.
Program co-chair of the 31st International Symposium on Algorithms and Computation, December 14-18, 2020, Hong Kong.
Program co-chair of the 30th Annual Symposium on Computational Geometry, June 8-11, 2014, Kyoto, Japan.
Advisory committee member of the International Symposium on Algorithms and Computation (ISAAC).
Chair of the Asian Association for Algorithms and Computation (AAAC).

Selected
University
Services

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 via dblp)

Frechet Distance

Siu-Wing Cheng and Haoqiang Huang. Frechet Distance in Subquadratic Time. Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, 2025.
Siu-Wing Cheng and Haoqiang Huang. Solving Frechet Distance Problems by Algebraic Geometric Methods. Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, 2024, 4502-4513.
Siu-Wing Cheng and Haoqiang Huang. Approximate Nearest Neighbor for Polygonal Curves under Frechet Distance. Proceedings of the International Colloquium on Automata, Languages, and Programming, 2023, 40:1-40:18.
Siu-Wing Cheng and Haoqiang Huang. Curve Simplifiation and Clustering under Frechet Distance. Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, 2023, 1414-1432.

Self-Improving Algorithms

Siu-Wing Cheng and Man Ting Wong. Self-Improving Voronoi Construction for a Hidden Mixture of Product Distributions. Proceedings of the 32nd International Symposium on Algorithms and Computation, 2021, 8:1-8:13.
Kai Jin, Siu-Wing Cheng, Man-Kwun Chiu, and Man Ting Wong. A Generalization of Self-Improving Algorithms. ACM Transactions on Algorithms, 18 (2022), 29:1-29:32.
Siu-Wing Cheng, Kai Jin, and Lie Yan. Extensions of Self-Improving Sorters. Algorithmica, 82 (2020), 88-106.

Max-Min Fair Allocation

Sheng-Yen Ko, Ho-Lin Chen, Siu-Wing Cheng, Wing-Kai Hon, and Chung-Shou Liao. General Max-Min Fair Allocation. Algorithmica, 86 (2024), 485-504.
Siu-Wing Cheng. Multistage Online Maxmin Allocation of Indivisible Entities. Theoretical Computer Science, 933 (2022), 104-113.
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. ACM Transactions on Algorithms, volume 18, issue 1, 2022, 3:1-63.
Siu-Wing Cheng and Man-Kit Lau. Adaptive Planar Point Location. SIAM Journal on Computing, 50 (2021), 1200-1247.
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.

Manifold Reconstruction

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