Siu Wing CHENG
鄭紹榮
PhD in Computer Science
University of Minnesota, 1992

Professor
Department of Computer Science and Engineering



(852) 2358 6973
scheng@ust.hk
Room 3551
Personal Web

---

Google Scholar
0nquEkQAAAAJ

ORCID
0000-0002-3557-9935

Scopus ID
7404686026




Research Interest Publications Projects Teaching Assignment RPG Supervision Space used




Research Interest

---

Algorithms
Geometry processing
Data structures
Theoretical computer science



Publications

---

All Years 151 2022 0 2021 3 2020 4 2019 2 2018 3 2017 6 2016 133

---

Expand All Collapse All


2021 3

Adaptive Planar Point Location
SIAM Journal on Computing, v. 50, (4), July 2021, p. 1200-1247
Cheng, Siu Wing; Lau, Man Kit Article
Fitting a graph to one-dimensional data
Theoretical Computer Science, v. 867, May 2021, p. 40-49
Cheng, Siu Wing; Cheong, Otfried; Lee, Taegyoung; Ren, Zhengtong Article
Self-Improving Voronoi Construction for a Hidden Mixture of Product Distributions
The 32nd International Symposium on Algorithms and Computation (ISAAC 2021), Fukuoka, Japan, 6-8 December, 2021
Cheng, Siu Wing; Wong, Man Ting Conference paper

2020 4

Extensions of Self-Improving Sorters
Algorithmica, v. 82 , (1), January 2020, p. 88-106
Cheng, Siu Wing; Jin, Kai; Yan, Lie Article
A generalization of self-improving algorithms
Leibniz International Proceedings in Informatics (LIPIcs), v. 164, June 2020, article number LIPIcs-SoCG-2020-29, p. 29:1-29:13
Cheng, Siu Wing; Chiu, Man-Kwun; Jin, Kai; Wong, Man Ting Conference paper
Dynamic Distribution-Sensitive Point Location
Leibniz International Proceedings in Informatics, LIPIcs, v. 164, June 2020, article number IPIcs-SoCG-2020-30, p. 30:1-30:13
Cheng, Siu Wing; Lau, Man Kit Conference paper
Fitting a Graph to One-Dimensional Data
The 32nd Canadian Conference on Computational Geometry, Saskatoon, Saskatchewan, Canada, 5-7 August 2020
Cheng, Siu Wing; Cheong, Otfried; Lee, Taegyoung Conference paper

2019 2

Implicit Manifold Reconstruction
Discrete And Computational Geometry, v. 62, (3), October 2019, p. 700-742
Cheng, Siu Wing; Chiu, Mankwun Article
Restricted Max-Min Allocation: Approximation and Integrality Gap
46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), v. 132, 1 July 2019, article number 38, p. 38:1-38:13, Series: Leibniz International Proceedings in Informatics (LIPIcs)
Cheng, Siu Wing; Mao, Yuchen Conference paper

2018 3

Minimax Regret 1-Median Problem in Dynamic Path Networks
Theory of Computing Systems, v. 62, (6), August 2018, p. 1392-1408
Higashikawa, Yuya; Cheng, Siu Wing; Kameda, Tsunehiko; Katoh, Naoki; Saburi, Shun Article
Extensions of Self-Improving Sorters
Leibniz International Proceedings in Informatics, LIPIcs, v. 123, 2018, p. 63:1-63:12
Cheng, Siu Wing; Yan, Lie Conference paper
Restricted max-min fair allocation
45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), v. 107, July 2018, article number 37, p. 37:1-37:13, Series: Leibniz International Proceedings in Informatics (LIPIcs)
Cheng, Siu Wing; Mao, Yuchen Conference paper

2017 6

A Fast and Simple Surface Reconstruction Algorithm
ACM Transactions on Algorithms, v. 13, (2), May 2017, article number 27
Cheng, Siu Wing; Jin, Jiongxin; Lau, Man Kit Article
Adaptive Point Location in Planar Convex Subdivisions
International Journal of Computational Geometry and Applications, v. 27, (1-2), June 2017, p. 3-12
Cheng, Siu Wing; Lau, Man Kit Article
Finding Largest Common Point Sets
International Journal of Computational Geometry and Applications, v. 27, (3), September 2017, p. 177-185
Yon, Juyoung; Cheng, Siu Wing; Cheong, Otfried; Antoine vigneron Article
Navigating Weighted Regions with Scattered Skinny Tetrahedra
International Journal of Computational Geometry and Applications, v. 27, (1-2), June 2017, p. 13-32
Cheng, Siu Wing; Chiu, Man kwun; Jin, Jiongxin; Vigneron, Antoine Article
Adaptive Planar Point Location
Proceedings of the 33rd International Symposium on Computational Geometry, v.77, June 2017, article number 30, p. 1-15
Cheng, Siu Wing; Lau, Man Kit Conference paper
Characterizing Minimal Rigidity of Square-Grid Frameworks with Holes
Proceedings of the 10th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, May 2017, p. 93-102
Cheng, Siu Wing; Higashikawa, Yuya; Katoh, Naoki; Slijoka, Adnan Conference paper

2016 7

A Faster Algorithm for Computing Straight Skeletons
ACM transactions on algorithms, v. 12, (3), June 2016, Article number 44
Cheng, Siu Wing; Liam, Mencel; Antoine, Vigneron Article
Tangent Estimation from Point Samples
Discrete and Computational Geometry, v. 56, (3), October 2016, p. 505-557
Cheng, Siu Wing; Chiu, Man Kwun Article
3D conforming delaunay triangulation
Encyclopedia of algorithms (2nd ed.) / Edited by Ming-Yang Kao. New York, NY : Springer New York, 2016, p. 499-502
Cheng, Siu-Wing Book chapter
Delaunay Mesh Generation
Delaunay Mesh Generation / Editor(s): Cheng, Siu Wing, Dey, Tamal K. and Shewchuk, Jonathan. CRC Press, 2016, p. 1-386
Cheng, Siu Wing; Dey, Tamal K.; Shewchuk, Jonathan Book chapter
Manifold reconstruction
Encyclopedia of algorithms (2nd ed.) / Edited by Ming-Yang Kao. New York, NY : Springer New York, 2016, p. 1185-1189
Cheng, Siu-Wing Book chapter
Approximating convex shapes with respect to symmetric difference under homotheties
Leibniz International Proceedings in Informatics, LIPIcs, v. 51, 2016, p. 63.1-63.15
Yon, Juyoung; Bae, Sang Won; Cheng, Siu Wing; Cheong, Otfried; Wilkinson, Bryan T. Conference paper
Minimax Regret 1-Median Problem in Dynamic Path Networks
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), v. 9843, 2016, p. 122-134
Higashikawa, Yuya; Cheng, Siu-Wing; Kameda, Tsunehiko; Katoh, Naoki; Saburi, Shun Conference paper

2015 7

Edge Flips in Surface Meshes
Discrete and Computational Geometry, v. 54, (1), July 2015, p. 110-151
Cheng, Siu-Wing; Jin, Jiongxin Article
Minimax regret 1-sink location problem in dynamic path networks
Theoretical Computer Science, v. 588, July 2015, p. 24-36
Higashikawa, Yuya; Augustine, John; Cheng, Siu-Wing; Golin, Mordecai Jay; Katoh, Naoki; Ni, Guanqun; Su, Bing; Xu, Yinfeng Article
Adaptive Point Location in Planar Convex Subdivisions
Lecture Notes in Computer Science, v. 9472, 2015, p. 14-22
Cheng, Siu Wing; Lau, Man Kit Conference paper
Deforming Surface Meshes
SEMA SIMAI Springer Series, v. 5, 2015, p. 69-89
Cheng, Siu Wing; Jin, Jiongxin Conference paper
Navigating Weighted Regions With Scattered Skinny Tetrahedra
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), v. 9472, 2015, p. 35-45
Cheng, Siu Wing; Chiu, Mankwun; Jin, Jiongxin; Vigneron, Antoine Conference paper
Piecewise Linear Approximation of Streaming Time Series Data with Max-error Guarantees
2015 IEEE 31st International Conference on Data Engineering (ICDE 2015), Institute of Electrical and Electronics Engineers (IEEE), 2015, p. 173-184
Luo, Ge; Yi, Ke; Cheng, Siu-Wing; Li, Zhenguo; Fan, Wei; He, Cheng; Mu, Yadong Conference paper
Triangulation Refinement and Approximate Shortest Paths in Weighted Regions
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, The Society for Industrial and Applied Mathematics (SIAM), 2015, p. 1626-1640
Cheng, Siu-Wing; Jin, Jiongxin; Antoine, Vigneron Conference paper

2014 7

Approximate Shortest Descending Paths
SIAM journal on computing, v. 43, (2), January 2014, p. 410-428
Cheng, Siu Wing; Jin, Jiongxin Article
Overlap of convex polytopes under rigid motion
Computational Geometry: Theory and Applications, v. 47, (1), 2014, p. 15-24
Ahn, Hee-Kap; Cheng, Siu-Wing; Kweon, Hyuk Jun; Yon, Juyoung Article
3D Conforming Delaunay Triangulation
Encyclopedia of Algorithms / Editor: Ming Yang Kao. New York : Springer Science, Business Media New York, 2014, p. 1-5
Cheng, Siu Wing Book chapter
Manifold Reconstruction
Encyclopedia of Algorithms / Editor: Ming Yang Kao. New York : Springer Science, Business Media New York, 2014, p. 1-6
Cheng, Siu Wing Book chapter
A Faster Algorithm for Computing Straight Skeletons
Lecture Notes in Computer Science, v. 8737 LNCS, 2014, p. 272-283
Cheng, Siuwing; Liam, Mencel; Antoine, Vigneron Conference paper
Implicit Manifold Reconstruction
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2014, p. 161-173
Cheng, Siu Wing; Chiu, Man Kwun Conference paper
Shortest Paths on Polyhedral Surfaces and Terrains
Proceedings of the forty-sixth annual ACM symposium on Theory of computing, New York, NY, USA : ACM, 2014, p. 373-382
Cheng, Siu Wing; Jin, Jiongxin Conference paper

2013 6

Maximum Overlap of Convex Polytopes under Translation
Computational Geometry: Theory and Applications, v. 46, (5), July 2013, p. 552-565
Ahn, Hee-Kap; Cheng, Siu-Wing; Reinbacher, Iris Article
Shape matching under rigid motion
Computational Geometry: Theory and Applications, v. 46, (6), 2013, p. 591-603
Cheng, Siu Wing; Lam, Chi Kit Article
Delaunay Mesh Generation
Delaunay Mesh Generation / By Siu-Wing Cheng, Tamal Krishna Dey, Jonathan Richard Shewchuk
Cheng, Siu Wing; Dey, Tamal Krishna; Shewchuk, Jonathan Richard Book
Algorithms and Computation
Lecture Notes in Computer Science LNCS, v. 8283
Cai, Leizhen; Cheng, Siu Wing; Lam, Tak Wah Conference paper
Approximate Shortest Descending Path
Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, v. 2013, 2013, p. 144-155
Cheng, Siu Wing; Jin, Jiongxin Conference paper
Minimax Regret 1-Sink Location Problems in Dynamic Path Networks
Theory and Applications of Models of Computation, 10th International Conference, TAMC 2013: Proceedings, Editors: T-H. Hubert Chan, Lap Chi Lau, Luca Trevisan. Berlin; Heidelberg : Springer-Verlag, 2013, p. 121-132, Part of the Lecture Notes in Computer Science book series (LNCS, volume 7876)
Cheng, Siu-Wing; Higashikawa, Yuya; Katoh, Naoki; Ni, Guanqun; Su, Bing; Xu, Yinfeng Conference paper

2012 4

Approximate Shortest Homotopic Paths in Weighted Regions
International Journal of Computational Geometry & Applications, v. 22, February 2012, p. 83-102
Cheng, Siu-Wing; Jin, Jiongxin; Vigneron, Antoine; Wang, Yajun Article
Range Searching on Uncertain Data
ACM transactions on algorithms, v. 8, (4), September 2012, Article 43
Agarwal, Pankaj K.; Cheng, Siu-Wing; Yi, Ke Article
A fast and simple surface reconstruction algorithm
Symposium on Computational Geometry 2012, University of North Carolina at Chapel Hill, June 2012, p. 69-78
Cheng, Siu Wing; Jin, Jiongxin; Lau, Man Kit Conference paper
Overlap of convex polytopes under rigid motion
Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), Hyderabad, India, Dec 15-17 2012, p. 498-509
Ahn, H.K.; Cheng, S.W.; Kweon, H.J.; Yon, J. Conference paper

2011 1

Edge Flips and Deforming Surface Meshes
COMPUTATIONAL GEOMETRY (SCG 11), 2011, p. 331-340
Cheng, Siu-Wing; Jin, Jiongxin Conference paper

2010 6

Delaunay Refinement for Piecewise Smooth Complexes
Discrete & Computational Geometry, v. 43, (1), 2010, JAN, p. 121-166
Cheng, Siu-Wing; Dey, Tamal K.; Ramos, Edgar A. Article
Querying Approximate Shortest Paths in Anisotropic Regions
SIAM Journal on Computing, v. 39, (5), 2010, p. 1888-1918
Cheng, Siu-Wing; Na, Hyeon-Suk; Vigneron, Antoine; Wang, Yajun Article
Approximate Homotopic Shortest Paths in Anisotropic Regions
International Symposium on Algorithms and Computation, Jeju, Korea, December 15-17, 2010, Lecture Notes in Computer Science 6507, pages 109-120
Cheng, Siu-Wing; Jin, Jiongxin; Vigneron, Antoine; Wang, Yajun Conference paper
Approximate shortest homotopic paths in weighted regions
Lecture Notes in Computer Science, v. 6507, (PART 2), 2010, p. 109-120
Cheng, S.W.; Jin, J.; Vigneron, A.; Wang, Y. Conference paper
Approximating the Average Stretch Factor of Geometric Graphs
Lecture Notes in Computer Science, v. 6506, 2010, p. 37-48
Cheng, Siu-Wing; Knauer, Christian; Langerman, Stefan; Smid, Michiel Conference paper
Maximum overlap of convex polytopes under translation
Lecture Notes in Computer Science, v. 6507, (PART 2), 2010, p. 97-108
Ahn, H.K.; Cheng, S.W.; Reinbacher, I. Conference paper

2009 5

Advances in Surface Meshing
数理解析研究所講究録, v. 1641, 2009, p. 125-134
Cheng, Siu Wing Article
Casting an Object with a Core
Algorithmica, v. 54, (1), 2009, MAY, p. 72-88
Ahn, Hee-Kap; Bae, Sang Won; Cheng, Siu-Wing; Chwa, Kyung-Yong Article
Dimension detection via slivers
Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, 4-6 January 2009, p. 1001-1010
Cheng, S.W.; Chiu, M.K. Conference paper
Indexing uncertain data
Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2009, p. 137-146
Agarwal, P.K.; Cheng, S.W.; Tao, Y.; Yi, K. Conference paper
Theory of a Practical Delaunay Meshing Algorithm for a Large Class of Domains
ALGORITHMS, ARCHITECTURES AND INFORMATION SYSTEMS SECURITY, v. 3, 2009, p. 25-42
Cheng, Siu-Wing; Dey, Tamal K.; Levine, Joshua Conference paper

2008 4

Approximate shortest paths in anisotropic regions
SIAM journal on computing, v. 38, (3), 2008, p. 802-824
Cheng, Siu-Wing; Na, Hyeon-Suk; Vigneron, Antoine; Wang, Yajun Article
PROVABLE DIMENSION DETECTION USING PRINCIPAL COMPONENT ANALYSIS
International journal of computational geometry & applications, v. 18, (5), 2008, OCT, p. 415-440
Cheng, Siu-Wing; Wang, Yajun; Wu, Zhaungzhi Article
A practical Delaunay meshing algorithm for a large class of domains
Proceedings of the 16th International Meshing Roundtable, 2008, p. 477-494
Cheng, Siu-Wing; Dev, Tamal K.; Levine, Joshua A. Conference paper
Maintaining deforming surface meshes
Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, 2008, p. 112-121
Cheng, S.W.; Dey, T.K. Conference paper

2007 5

Motorcycle graphs and straight skeletons
Algorithmica, v. 47, (2), 2007, FEB, p. 159-182
Cheng, Siu-Wing; Vigneron, Antoine Article
Sampling and meshing a surface with guaranteed topology and geometry
SIAM journal on computing, v. 37, (4), 2007, Sep, p. 1199-1227
Cheng, Siu-Wing; Dey, Tamal K.; Ramos, Edgar A.; Ray, Tathagata Article
Approximate shortest paths in anisotropic regions
Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, 2007, p. 766-774
Cheng, Siu-Wing; Na, Hyeon-Suk; Vigneron, Antoine; Wang, Yajun Conference paper
Delaunay Refinement for Piecewise Smooth Complexes
PROCEEDINGS OF THE EIGHTEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 2007, p. 1096-1105
Cheng, Siu-Wing; Dey, Tamal K.; Ramos, Edgar A. Conference paper
Querying approximate shortest paths in anisotropic regions
Proceedings of the Annual Symposium on Computational Geometry, 2007, p. 84-91
Cheng, S.W.; Na, H.S.; Vigneron, A.; Wang, Y. Conference paper

2006 4

Casting with skewed ejection direction
Algorithmica, v. 44, (4), 2006, May, p. 325-342
Ahn, HK; Cheng, SW; Cheong, O. Article
On the sizes of Delaunay meshes
COMPUTATIONAL geometry-theory and APPLICATIONS, v. 33, (3), 2006, FEB, p. 130-138
Cheng, SW Article
Three-dimensional Delaunay mesh generation
Discrete & Computational Geometry, v. 36, (3), 2006, OCT, p. 419-456
Cheng, Siu-Wing; Poon, Sheung-Hung Article
Anisotropic surface meshing
Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, 2006, p. 202-211
Cheng, S.W.; Dey, T.K.; Ramos, E.A.; Wenger, R. Conference paper

2005 8

Casting an Object with a Core
Lecture Notes in Computer Science, v. 3827, 2005, p. 40-49
Ahn, HK; Bae, SW; Cheng, SW; Chwa, KY Article
Curve reconstruction from noisy samples
COMPUTATIONAL geometry-theory and APPLICATIONS, v. 31, (1-2), 2005, MAY, p. 63-100
Cheng, SW; Funke, S.; Golin, M.; Kumar, P.; Poon, SH; Ramos, E. Article
Energy efficient broadcasting and multicasting in static wireless ad hoc networks
Lecture Notes in Computer Science, v. 3521, 2005, p. 16-25
Cheng, SW; Jia, XH; Hung, F.; Wang, YJ Article
Quality meshing of polyhedra with small angles
International journal of computational geometry & applications, v. 15, (4), 2005, AUG, p. 421-461
Cheng, SW; Dey, TK; Ramos, EA; Ray, T. Article
Planar Straight Line Graphs
Handbook of Data Structures and Applications / Edited by Dinesh P. Mehta, Sartaj Sahni. Boca Raton, Fla.: Chapman & Hall/CRC, 2005, p. 17-1 - 17-17
Cheng, Siu-Wing Book chapter
Manifold reconstruction from point samples
Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, 2005, p. 1018-1027
Cheng, S.W.; Dey, T.K.; Ramos, E.A. Conference paper
Provable dimension detection using principal component analysis
Proceedings of the Annual Symposium on Computational Geometry, 2005, p. 208-217
Cheng, S.W.; Wang, Y.; Wu, Z. Conference paper
Weighted Delaunay refinement for polyhedra with small angles
PROCEEDINGS OF THE 14TH INTERNATIONAL MESHING ROUNDTABLE, 2005, p. 325-342
Cheng, SW; Dey, TK; Ray, T. Conference paper

2004 7

Competitive facility location: the Voronoi game
Theoretical Computer Science, v. 310, (1-3), 2004, JAN 1, p. 457-467
Ahn, HK; Cheng, SW; Cheong, O.; Golin, M.; van Oostrum, R. Article
Hierarchical decompositions and circular ray shooting in simple polygons
Discrete & Computational Geometry, v. 32, (3), 2004, OCT, p. 401-415
Cheng, SW; Cheong, O.; Everett, H.; van Oostrum, R. Article
Hierarchy of surface models and irreducible triangulations
Computational Geometry: Theory and Applications, v. 27, (2), 2004, Feb, p. 135-150
Cheng, Siu Wing; Dey, Tamal K.; Poon, Sheung-Hung Article
The reflex-free hull
International journal of computational geometry & applications, v. 14, (6), 2004, DEC, p. 453-474
Ahn, HK; Cheng, SW; Cheong, O.; Snoeyink, J. Article
On the Sizes of Delaunay Meshes
Proceedings of the International Symposium on Voronoi Diagrams in Science and Engineering, 2004, 104-113
Cheng, Siu-Wing Conference paper
Quality meshing for polyhedra with small angles
Proceedings of the Annual Symposium on Computational Geometry, 2004, p. 290-299
Cheng, S.W.; Dey, T.K.; Ramos, E.A.; Ray, T. Conference paper
Sampling and meshing a surface with guaranteed topology and geometry
Proceedings of the Annual Symposium on Computational Geometry, 2004, p. 280-289
Cheng, S.W.; Dey, T.K.; Ramos, E.A.; Ray, T. Conference paper

2003 3

Quality meshing with weighted delaunay refinement
SIAM journal on computing, v. 33, (1), 2003, p. 69-93
Cheng, SW; Dey, TK Article
Curve reconstruction from noisy samples
Proceedings of the Annual Symposium on Computational Geometry, 2003, p. 302-311
Cheng, S.W.; Funke, S.; Golin, M.; Kumar, P.; Poon, S.H.; Ramos, E. Conference paper
Graded conforming delaunay tetrahedralization with bounded radius-edge ratio
Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, 2003, p. 295-304
Cheng, S.W.; Poon, S.H. Conference paper

2002 6

Hierarchy of surface models and irreducible triangulations
Lecture Notes in Computer Science, v. 2518, 2002, p. 286-295
Cheng, SW; Dey, TK; Poon, SH Article
Quadtree, ray shooting and approximate minimum weight Steiner triangulation
COMPUTATIONAL geometry-theory and APPLICATIONS, v. 23, (2), 2002, SEP, p. 99-116
Cheng, Siu Wing; Lee, Kamhing Article
Separating an object from its cast
Computer-Aided Design, v. 34, (8), 2002, JUL, p. 547-559
Ahn, HK; de Berg, M.; Bose, P.; Cheng, SW; Halperin, D.; Matousek, J.; Schwarzkopf, O. Article
Hierarchy of Surface Models and Irreducible Triangulation
Proceedings of the 13th International Symposium on Algorithms and Computation, 286-295
Cheng, Siu-Wing; Dey, Tamal K.; Poon, Sheung-Hung Conference paper
Motorcycle graphs and straight skeletons
PROCEEDINGS OF THE THIRTEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 2002, p. 156-165
Cheng, SW; Vigneron, A. Conference paper
Quality meshing with weighted Delaunay refinement
PROCEEDINGS OF THE THIRTEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 2002, p. 137-146
Cheng, SW; Dey, TK Conference paper

2001 5

Approximation algorithm for multiple-tool milling
International journal of computational geometry & applications, v. 11, (3), 2001, JUN, p. 339-372
Arya, Sunil; Cheng, SW; Mount, DM Article
Competitive facility location along a highway
Lecture Notes in Computer Science, v. 2108, 2001, p. 237-246
Ahn, HK; Cheng, SW; Cheong, O.; Golin, M.; van Ostrum, R. Article
Design and analysis of planar shape deformation
COMPUTATIONAL geometry-theory and APPLICATIONS, v. 19, (2-3), 2001, JUL, p. 205-218
Cheng, SW; Edelsbrunner, H.; Fu, P.; Lam, KP Article
On β-skeleton as a subgraph of the minimum weight triangulation
Theoretical Computer Science, v. 262, (1-2), 2001, JUL 6, p. 459-471
Cheng, SW; Xu, XF Article
Competitive facility location: the Voronoi game
Computing and Combinatorics, Proc 7th Annual International Conference (COCOON 2001), v. 2108, 2001, p. 237-246
van Oostrum, R.; Ahn, Hee-Kap; Cheng, Siu Wing; Cheong, O.; Golin, Mordecai Jay Conference paper

2000 5

Efficient Expected-Case Algorithms for Planar Point Location
Lecture Notes in Computer Science, v. 1851, 2000, p. 353-366
Arya, Sunil; Cheng, Siu-Wing; Mount, David M.; Ramesh, H. Article
LMT-skeleton heuristics for several new classes of optimal triangulations
COMPUTATIONAL geometry-theory and APPLICATIONS, v. 17, (1-2), 2000, OCT, p. 51-68
Dai, Yang; Katoh, Naoki; Cheng, Siu-Wing Article
Sliver exudation
Journal of the ACM, v. 47, (5), 2000, SEP, p. 883-904
Cheng, Siu-Wing; Dey, Tamal K.; Edelsbrunner, Herbert; Facello, Michael A.; Teng, Shang-Hua Article
The Steiner tree problem for terminals on the boundary of a rectilinear polygon
Theoretical Computer Science, v. 237, (1-2), 2000, APR 28, p. 213-238
Cheng, SW Article
Exact Steiner Trees in Graphs and Grid Graphs
Advances in Steiner Trees Combinatorial Optimization Volume 6 / Du Ding-Zhu, Smith JM, Rubinstein JH. US: Springer US, 2000, p. 137-162
Cheng, Siu Wing Book chapter

1999 8

A triangulation for optimal strip decomposition in simple polygons
The second ACM Hong Kong postgraduate research day, 1999
Cheng, Siu Wing; Cheong, Jae-Sook Article
Hierachical Vertical Decompositions, Ray Shooting, and Circular Arc Queries in Simple Polygons
SCG 99' Proceedings of the 15th Annual ACM Symposium on Computational Geometry, 227-236
Cheng, Siu-Wing; Everett, Hazel; Cheong, Otfried; Oostrum, Rene Van Article
Improved constructions of Delaunay based contour surfaces
Proceedings of the Symposium on Solid Modeling and Applications, 1999, p. 322-323
Cheng, Siu-Wing; Dey, Tamal K. Article
Approximate minimum weight Steiner triangulation in three dimensions
Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, 1999, p. 205-214
Cheng, Siu-Wing; Dey, Tamal K. Conference paper
Casting with skewed ejection direction revisited
CCCG, 1999
Ahn, Hee-Kap; Chen, Siu Wing; Cheong, Otfried Conference paper
Hierarchical vertical decompositions, ray shooting, and circular arc queries in simple polygons
PROC ANNU SYMP COMPUT GEOM, pp. 227-236. 1999
Cheng, Siu-Wing; Everett, Hazel; Cheong, Otfried; van Oostrum, Rene Conference paper
Hierarchical vertical decompositions, ray shooting, and circular arc queries in simple polygons
Proceedings of the fifteenth annual symposium on Computational geometry; 13-16 June 1999
Cheng, Siu-Wing; Everett, Hazel; Cheong, Otfried; van Oostrum, Rene Conference paper
Sliver Exudation
Proceedings of the Annual Symposium on Computational Geometry, 1999, p. 1-13
Cheng, Siu-Wing; Dey, Tamal Krishna; Edelsbrunner, Herbert; Facello, Michael A.; Teng, Shang-Hua Conference paper

1998 5

Minimum dominating sets of intervals on lines
Algorithmica (New York), v. 20, (3), 1998, p. 294-308
Cheng, Siu Wing; Kaminski, Michael; Zaks, Shmuel Article
Quadtree decomposition, Steiner triangulation, and ray shooting
Lecture Notes in Computer Science, v. 1533, 1998, p. 367-376
Cheng, SW; Lee, KH Article
Approximation algorithms for multiple-tool miling
Proceedings of the fourteenth annual symposium on Computational geometry, 07-10 June 1998, p. 297-306
Arya, Sunil; Cheng, Siu Wing; Mount, David M. Conference paper
Casting with Skewed Ejection Direction
Lecture Notes in Computer Science, v. 1533 LNCS, 1998, p. 139-150
Ahn, Heekap; Cheng, Siu Wing; Cheong, Otfried Conference paper
Design and analysis of planar shape deformation
Proceedings of the fourteenth annual symposium on Computational geometry, 7-10 June 1998, p. 29-38
Cheng, Siu-Wing; Edelsbrunner, Herbert; Fu, Ping; Lam, Ka-Po Conference paper

1997 1

Separating an Object from its Cast
Proceedings of the 13th Annual Symposium on Computational Geometry (SOCG), Nice, France, June 7-10 1997, p. 221-230
Ahn, Hee-Kap; Berg, Mark de; Bose, Prosenjit; Cheng, Siu-Wing; Halperin, Dan; Matousek, Jiri; Schwarzkopf, Otfried Conference paper

1996 5

Triangulations intersect nicely
Discrete & Computational Geometry, v. 16, (4), 1996, DEC, p. 339-359
Aichholzer, O.; Aurenhammer, F.; Cheng, SW; Katoh, N.; Rote, G.; Taschwer, M.; Xu, YF Article
Widest empty L-shaped corridor
Information Processing Letters, v. 58, (6), 1996, JUN 24, p. 277-283
Cheng, SW Article
A Study of the LMT-Skeleton
Lecture Notes in Computer Science, v. 1178, 1996, p. 256-265
Cheng, Siu Wing; Katoh, Naoki; Sugai, Manabu Conference paper
Approaching the largest β-skeleton within a minimum weight triangulation
Proceedings of the Annual Symposium on Computational Geometry, 1996, p. 196-203
Cheng, Siu-Wing; Xu, Yin-Feng Conference paper
Isomorphism testing and display of symmetries in dynamic trees
PROCEEDINGS OF THE SEVENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 1996, p. 202-211
Cheng, SW; Ng, MP Conference paper

1995 5

Constrained Independence System and Triangulations of Planar Point Sets
Lecture Notes in Computer Science, v. 959, 1995, p. 41-50
Cheng, Siu Wing; Xu, Yinfeng Article
Minimum Dominating Sets of Intervals on Lines
Lecture Notes in Computer Science, v. 959, 1995, p. 520-529
Cheng, Siu Wing; Kaminski, Michael; Zaks, Shmuel Article
A Fast Algorithm for Computing Optimal Rectilinear Steiner Trees for External Point Sets
Lecture Notes in Computer Science4 / v. 1004, 1995, p. 322-331
Cheng, Siu Wing; Tang, Chi Keung Book chapter
A Fast Algorithm for Computing Optimal Rectilinear Steiner Trees for Extremal Point Sets
Proc. International Symposium on Algorithm and Computation, December 1995
Cheng, Siu Wing; Tang, Chi Keung Conference paper
Expected case analysis of-skeletons with applications to the construction of minimum weight triangulations
Proc. 7th Canad. Conf. Comput. Geom, 1995, p. 279-284
Cheng, Siu Wing; Golin, Mordecai J.; Tsang, Jeffrey CF Conference paper

1994 2

Modifications of Competitive Group Testing
SIAM Journal on Computing, v. 23, 1994, p. 82-96
Du, Ding-Zhu; Xue, Guo-Liang; Sun, Shang-Zhi; Cheng, Siu Wing Article
The Role of Long and Short Paths in Circuit Performance Optimization
IEEE Transactions on Computer-Aided Design, v. 13, 1994, p. 857-864
Cheng, Siu Wing; Chen, Hsi-Chuan; Du, David H.C.; Lim, Andrew Article

1993 6

Optimal Joining of Compacted Cells
IEEE Transactions on Computers, v. 42, 1993, p. 597-607
Lim, Andrew; Cheng, Siu Wing; Sahni, Sartaj Article
Performance Oriented Rectilinear Steiner Trees
Eletrik, v. 1, 1993, p. 137-152
Lim, Andrew; Cheng, Siu Wing; Wu, Ching-Ting Article
SINGLE JOG MINIMUM AREA JOINING OF COMPACTED CELLS
Information Processing Letters, v. 47, (4), 1993, SEP 27, p. 167-172
LIM, A.; CHEE, YM; CHENG, SW Article
A Path Sensitization Approach to Area Optimization
Proceedings of IEEE International Conference on Computer Design: VLSI in Computers and Processors, 1993, p. 73-76
Chen, Hsi-Chuan; Cheng, Siu Wing; Hsu, Yaun-Chung; Du, David H.C. Conference paper
Optimal Rectilinear Steiner Tree for Extremal Point Sets
Proceedings of the 4th Annual Symposium on Algorithms and Computation (ISAAC), 1993, p. 523-532
Cheng, Siu Wing; Lim, Andrew; Wu, Ching-Ting Conference paper
Performance Oriented Rectilinear Steiner Trees
Proceedings of the 30th Design Automation Conference (DAC), 1993, p. 171-176
Lim, Andrew; Cheng, Siu Wing; Wu, Ching-Ting Conference paper

1992 6

Algorithms for Ray-Shooting and Intersection Searching
Journal of Algorithms, v. 13, 1992, p. 670-692
Cheng, Siu Wing; Janardan, Ravi Article
Efficient Distributed Algorithms for Single-Source Shortest Paths and Related Problems on Plane Networks
Mathematical Systems Theory, v. 25, 1992, p. 93-122
Janardan, Ravi; Cheng, Siu Wing Article
New Results on Dynamic Planar Point Location
SIAM Journal on Computing, v. 21, 1992, p. 972-999
Cheng, Siu Wing; Janardan, Ravi Article
Circuit enhancement by eliminating long false paths
Proceedings of the 29th Design Automation Conference (DAC), 1992, p. 249-252
Chen, Hsi-Chuan; Du, David H.C.; Cheng, Siu Wing Conference paper
Optimal Joining of Compacted Cells
Proceedings of the 1992 Brown/MIT Conference on Advanced Research in VLSI and Parallel Systems, 1992, p. 99-112
Lim, Andrew; Cheng, Siu Wing; Sahni, Sartaj Conference paper
The Role of Long and Short Paths in Circuit Performance Optimization
Proceedings of the 29th Design Automation Conference (DAC), 1992, p. 543-548
Cheng, Siu Wing; Chen, Hsi-Chuan; Du, David H.C.; Lim, Andrew Conference paper

1991 2

Efficient Maintenance of the Union of Intervals on a Line, with Applications
Journal of Algorithms, v. 12, 1991, p. 57-74
Cheng, Siu Wing; Janardan, Ravi Article
Space-Efficient Ray-Shooting and Intersection Searching: Algorithms, Dynamization, and Applications
Proceedings of the 2nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 1991, p. 7-16
Cheng, Siu Wing; Janardan, Ravi Conference paper

1990 3

Efficient Dynamic Algorithms for some Geometric Intersection Problems
Information Processing Letters, v. 36, 1990, p. 251-258
Cheng, Siu Wing; Janardan, Ravi Article
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, p. 74-83
Cheng, Siu Wing; Janardan, Ravi Conference paper
New results on Dynamic Planar Point Location
Proceedings of the 31st Annual IEEE Symposium on Foundations of Computer Science (FOCS), 1990, p. 96-105
Cheng, Siu Wing; Janardan, Ravi Conference paper


Expand All Collapse All


Article 2

Adaptive Planar Point Location
SIAM Journal on Computing, v. 50, (4), July 2021, p. 1200-1247
Cheng, Siu Wing; Lau, Man Kit
Fitting a graph to one-dimensional data
Theoretical Computer Science, v. 867, May 2021, p. 40-49
Cheng, Siu Wing; Cheong, Otfried; Lee, Taegyoung; Ren, Zhengtong

Conference paper 1

Self-Improving Voronoi Construction for a Hidden Mixture of Product Distributions
The 32nd International Symposium on Algorithms and Computation (ISAAC 2021), Fukuoka, Japan, 6-8 December, 2021
Cheng, Siu Wing; Wong, Man Ting


Expand All Collapse All


Article 1

Extensions of Self-Improving Sorters
Algorithmica, v. 82 , (1), January 2020, p. 88-106
Cheng, Siu Wing; Jin, Kai; Yan, Lie

Conference paper 3

A generalization of self-improving algorithms
Leibniz International Proceedings in Informatics (LIPIcs), v. 164, June 2020, article number LIPIcs-SoCG-2020-29, p. 29:1-29:13
Cheng, Siu Wing; Chiu, Man-Kwun; Jin, Kai; Wong, Man Ting
Dynamic Distribution-Sensitive Point Location
Leibniz International Proceedings in Informatics, LIPIcs, v. 164, June 2020, article number IPIcs-SoCG-2020-30, p. 30:1-30:13
Cheng, Siu Wing; Lau, Man Kit
Fitting a Graph to One-Dimensional Data
The 32nd Canadian Conference on Computational Geometry, Saskatoon, Saskatchewan, Canada, 5-7 August 2020
Cheng, Siu Wing; Cheong, Otfried; Lee, Taegyoung


Expand All Collapse All


Article 1

Implicit Manifold Reconstruction
Discrete And Computational Geometry, v. 62, (3), October 2019, p. 700-742
Cheng, Siu Wing; Chiu, Mankwun

Conference paper 1

Restricted Max-Min Allocation: Approximation and Integrality Gap
46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), v. 132, 1 July 2019, article number 38, p. 38:1-38:13, Series: Leibniz International Proceedings in Informatics (LIPIcs)
Cheng, Siu Wing; Mao, Yuchen


Expand All Collapse All


Article 1

Minimax Regret 1-Median Problem in Dynamic Path Networks
Theory of Computing Systems, v. 62, (6), August 2018, p. 1392-1408
Higashikawa, Yuya; Cheng, Siu Wing; Kameda, Tsunehiko; Katoh, Naoki; Saburi, Shun

Conference paper 2

Extensions of Self-Improving Sorters
Leibniz International Proceedings in Informatics, LIPIcs, v. 123, 2018, p. 63:1-63:12
Cheng, Siu Wing; Yan, Lie
Restricted max-min fair allocation
45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), v. 107, July 2018, article number 37, p. 37:1-37:13, Series: Leibniz International Proceedings in Informatics (LIPIcs)
Cheng, Siu Wing; Mao, Yuchen


Expand All Collapse All


Article 4

A Fast and Simple Surface Reconstruction Algorithm
ACM Transactions on Algorithms, v. 13, (2), May 2017, article number 27
Cheng, Siu Wing; Jin, Jiongxin; Lau, Man Kit
Adaptive Point Location in Planar Convex Subdivisions
International Journal of Computational Geometry and Applications, v. 27, (1-2), June 2017, p. 3-12
Cheng, Siu Wing; Lau, Man Kit
Finding Largest Common Point Sets
International Journal of Computational Geometry and Applications, v. 27, (3), September 2017, p. 177-185
Yon, Juyoung; Cheng, Siu Wing; Cheong, Otfried; Antoine vigneron
Navigating Weighted Regions with Scattered Skinny Tetrahedra
International Journal of Computational Geometry and Applications, v. 27, (1-2), June 2017, p. 13-32
Cheng, Siu Wing; Chiu, Man kwun; Jin, Jiongxin; Vigneron, Antoine

Conference paper 2

Adaptive Planar Point Location
Proceedings of the 33rd International Symposium on Computational Geometry, v.77, June 2017, article number 30, p. 1-15
Cheng, Siu Wing; Lau, Man Kit
Characterizing Minimal Rigidity of Square-Grid Frameworks with Holes
Proceedings of the 10th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, May 2017, p. 93-102
Cheng, Siu Wing; Higashikawa, Yuya; Katoh, Naoki; Slijoka, Adnan


Expand All Collapse All


Article 2

A Faster Algorithm for Computing Straight Skeletons
ACM transactions on algorithms, v. 12, (3), June 2016, Article number 44
Cheng, Siu Wing; Liam, Mencel; Antoine, Vigneron
Tangent Estimation from Point Samples
Discrete and Computational Geometry, v. 56, (3), October 2016, p. 505-557
Cheng, Siu Wing; Chiu, Man Kwun

Book chapter 3

3D conforming delaunay triangulation
Encyclopedia of algorithms (2nd ed.) / Edited by Ming-Yang Kao. New York, NY : Springer New York, 2016, p. 499-502
Cheng, Siu-Wing
Delaunay Mesh Generation
Delaunay Mesh Generation / Editor(s): Cheng, Siu Wing, Dey, Tamal K. and Shewchuk, Jonathan. CRC Press, 2016, p. 1-386
Cheng, Siu Wing; Dey, Tamal K.; Shewchuk, Jonathan
Manifold reconstruction
Encyclopedia of algorithms (2nd ed.) / Edited by Ming-Yang Kao. New York, NY : Springer New York, 2016, p. 1185-1189
Cheng, Siu-Wing

Conference paper 2

Approximating convex shapes with respect to symmetric difference under homotheties
Leibniz International Proceedings in Informatics, LIPIcs, v. 51, 2016, p. 63.1-63.15
Yon, Juyoung; Bae, Sang Won; Cheng, Siu Wing; Cheong, Otfried; Wilkinson, Bryan T.
Minimax Regret 1-Median Problem in Dynamic Path Networks
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), v. 9843, 2016, p. 122-134
Higashikawa, Yuya; Cheng, Siu-Wing; Kameda, Tsunehiko; Katoh, Naoki; Saburi, Shun


Expand All Collapse All


Article 2

Edge Flips in Surface Meshes
Discrete and Computational Geometry, v. 54, (1), July 2015, p. 110-151
Cheng, Siu-Wing; Jin, Jiongxin
Minimax regret 1-sink location problem in dynamic path networks
Theoretical Computer Science, v. 588, July 2015, p. 24-36
Higashikawa, Yuya; Augustine, John; Cheng, Siu-Wing; Golin, Mordecai Jay; Katoh, Naoki; Ni, Guanqun; Su, Bing; Xu, Yinfeng

Conference paper 5

Adaptive Point Location in Planar Convex Subdivisions
Lecture Notes in Computer Science, v. 9472, 2015, p. 14-22
Cheng, Siu Wing; Lau, Man Kit
Deforming Surface Meshes
SEMA SIMAI Springer Series, v. 5, 2015, p. 69-89
Cheng, Siu Wing; Jin, Jiongxin
Navigating Weighted Regions With Scattered Skinny Tetrahedra
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), v. 9472, 2015, p. 35-45
Cheng, Siu Wing; Chiu, Mankwun; Jin, Jiongxin; Vigneron, Antoine
Piecewise Linear Approximation of Streaming Time Series Data with Max-error Guarantees
2015 IEEE 31st International Conference on Data Engineering (ICDE 2015), Institute of Electrical and Electronics Engineers (IEEE), 2015, p. 173-184
Luo, Ge; Yi, Ke; Cheng, Siu-Wing; Li, Zhenguo; Fan, Wei; He, Cheng; Mu, Yadong
Triangulation Refinement and Approximate Shortest Paths in Weighted Regions
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, The Society for Industrial and Applied Mathematics (SIAM), 2015, p. 1626-1640
Cheng, Siu-Wing; Jin, Jiongxin; Antoine, Vigneron


Expand All Collapse All


Article 2

Approximate Shortest Descending Paths
SIAM journal on computing, v. 43, (2), January 2014, p. 410-428
Cheng, Siu Wing; Jin, Jiongxin
Overlap of convex polytopes under rigid motion
Computational Geometry: Theory and Applications, v. 47, (1), 2014, p. 15-24
Ahn, Hee-Kap; Cheng, Siu-Wing; Kweon, Hyuk Jun; Yon, Juyoung

Book chapter 2

3D Conforming Delaunay Triangulation
Encyclopedia of Algorithms / Editor: Ming Yang Kao. New York : Springer Science, Business Media New York, 2014, p. 1-5
Cheng, Siu Wing
Manifold Reconstruction
Encyclopedia of Algorithms / Editor: Ming Yang Kao. New York : Springer Science, Business Media New York, 2014, p. 1-6
Cheng, Siu Wing

Conference paper 3

A Faster Algorithm for Computing Straight Skeletons
Lecture Notes in Computer Science, v. 8737 LNCS, 2014, p. 272-283
Cheng, Siuwing; Liam, Mencel; Antoine, Vigneron
Implicit Manifold Reconstruction
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2014, p. 161-173
Cheng, Siu Wing; Chiu, Man Kwun
Shortest Paths on Polyhedral Surfaces and Terrains
Proceedings of the forty-sixth annual ACM symposium on Theory of computing, New York, NY, USA : ACM, 2014, p. 373-382
Cheng, Siu Wing; Jin, Jiongxin


Expand All Collapse All


Article 2

Maximum Overlap of Convex Polytopes under Translation
Computational Geometry: Theory and Applications, v. 46, (5), July 2013, p. 552-565
Ahn, Hee-Kap; Cheng, Siu-Wing; Reinbacher, Iris
Shape matching under rigid motion
Computational Geometry: Theory and Applications, v. 46, (6), 2013, p. 591-603
Cheng, Siu Wing; Lam, Chi Kit

Book 1

Delaunay Mesh Generation
Delaunay Mesh Generation / By Siu-Wing Cheng, Tamal Krishna Dey, Jonathan Richard Shewchuk
Cheng, Siu Wing; Dey, Tamal Krishna; Shewchuk, Jonathan Richard

Conference paper 3

Algorithms and Computation
Lecture Notes in Computer Science LNCS, v. 8283
Cai, Leizhen; Cheng, Siu Wing; Lam, Tak Wah
Approximate Shortest Descending Path
Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, v. 2013, 2013, p. 144-155
Cheng, Siu Wing; Jin, Jiongxin
Minimax Regret 1-Sink Location Problems in Dynamic Path Networks
Theory and Applications of Models of Computation, 10th International Conference, TAMC 2013: Proceedings, Editors: T-H. Hubert Chan, Lap Chi Lau, Luca Trevisan. Berlin; Heidelberg : Springer-Verlag, 2013, p. 121-132, Part of the Lecture Notes in Computer Science book series (LNCS, volume 7876)
Cheng, Siu-Wing; Higashikawa, Yuya; Katoh, Naoki; Ni, Guanqun; Su, Bing; Xu, Yinfeng


Expand All Collapse All


Article 2

Approximate Shortest Homotopic Paths in Weighted Regions
International Journal of Computational Geometry & Applications, v. 22, February 2012, p. 83-102
Cheng, Siu-Wing; Jin, Jiongxin; Vigneron, Antoine; Wang, Yajun
Range Searching on Uncertain Data
ACM transactions on algorithms, v. 8, (4), September 2012, Article 43
Agarwal, Pankaj K.; Cheng, Siu-Wing; Yi, Ke

Conference paper 2

A fast and simple surface reconstruction algorithm
Symposium on Computational Geometry 2012, University of North Carolina at Chapel Hill, June 2012, p. 69-78
Cheng, Siu Wing; Jin, Jiongxin; Lau, Man Kit
Overlap of convex polytopes under rigid motion
Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), Hyderabad, India, Dec 15-17 2012, p. 498-509
Ahn, H.K.; Cheng, S.W.; Kweon, H.J.; Yon, J.


Expand All Collapse All


Conference paper 1

Edge Flips and Deforming Surface Meshes
COMPUTATIONAL GEOMETRY (SCG 11), 2011, p. 331-340
Cheng, Siu-Wing; Jin, Jiongxin


Expand All Collapse All


Article 2

Delaunay Refinement for Piecewise Smooth Complexes
Discrete & Computational Geometry, v. 43, (1), 2010, JAN, p. 121-166
Cheng, Siu-Wing; Dey, Tamal K.; Ramos, Edgar A.
Querying Approximate Shortest Paths in Anisotropic Regions
SIAM Journal on Computing, v. 39, (5), 2010, p. 1888-1918
Cheng, Siu-Wing; Na, Hyeon-Suk; Vigneron, Antoine; Wang, Yajun

Conference paper 4

Approximate Homotopic Shortest Paths in Anisotropic Regions
International Symposium on Algorithms and Computation, Jeju, Korea, December 15-17, 2010, Lecture Notes in Computer Science 6507, pages 109-120
Cheng, Siu-Wing; Jin, Jiongxin; Vigneron, Antoine; Wang, Yajun
Approximate shortest homotopic paths in weighted regions
Lecture Notes in Computer Science, v. 6507, (PART 2), 2010, p. 109-120
Cheng, S.W.; Jin, J.; Vigneron, A.; Wang, Y.
Approximating the Average Stretch Factor of Geometric Graphs
Lecture Notes in Computer Science, v. 6506, 2010, p. 37-48
Cheng, Siu-Wing; Knauer, Christian; Langerman, Stefan; Smid, Michiel
Maximum overlap of convex polytopes under translation
Lecture Notes in Computer Science, v. 6507, (PART 2), 2010, p. 97-108
Ahn, H.K.; Cheng, S.W.; Reinbacher, I.


Expand All Collapse All


Article 2

Advances in Surface Meshing
数理解析研究所講究録, v. 1641, 2009, p. 125-134
Cheng, Siu Wing
Casting an Object with a Core
Algorithmica, v. 54, (1), 2009, MAY, p. 72-88
Ahn, Hee-Kap; Bae, Sang Won; Cheng, Siu-Wing; Chwa, Kyung-Yong

Conference paper 3

Dimension detection via slivers
Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, 4-6 January 2009, p. 1001-1010
Cheng, S.W.; Chiu, M.K.
Indexing uncertain data
Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2009, p. 137-146
Agarwal, P.K.; Cheng, S.W.; Tao, Y.; Yi, K.
Theory of a Practical Delaunay Meshing Algorithm for a Large Class of Domains
ALGORITHMS, ARCHITECTURES AND INFORMATION SYSTEMS SECURITY, v. 3, 2009, p. 25-42
Cheng, Siu-Wing; Dey, Tamal K.; Levine, Joshua


Expand All Collapse All


Article 2

Approximate shortest paths in anisotropic regions
SIAM journal on computing, v. 38, (3), 2008, p. 802-824
Cheng, Siu-Wing; Na, Hyeon-Suk; Vigneron, Antoine; Wang, Yajun
PROVABLE DIMENSION DETECTION USING PRINCIPAL COMPONENT ANALYSIS
International journal of computational geometry & applications, v. 18, (5), 2008, OCT, p. 415-440
Cheng, Siu-Wing; Wang, Yajun; Wu, Zhaungzhi

Conference paper 2

A practical Delaunay meshing algorithm for a large class of domains
Proceedings of the 16th International Meshing Roundtable, 2008, p. 477-494
Cheng, Siu-Wing; Dev, Tamal K.; Levine, Joshua A.
Maintaining deforming surface meshes
Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, 2008, p. 112-121
Cheng, S.W.; Dey, T.K.


Expand All Collapse All


Article 2

Motorcycle graphs and straight skeletons
Algorithmica, v. 47, (2), 2007, FEB, p. 159-182
Cheng, Siu-Wing; Vigneron, Antoine
Sampling and meshing a surface with guaranteed topology and geometry
SIAM journal on computing, v. 37, (4), 2007, Sep, p. 1199-1227
Cheng, Siu-Wing; Dey, Tamal K.; Ramos, Edgar A.; Ray, Tathagata

Conference paper 3

Approximate shortest paths in anisotropic regions
Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, 2007, p. 766-774
Cheng, Siu-Wing; Na, Hyeon-Suk; Vigneron, Antoine; Wang, Yajun
Delaunay Refinement for Piecewise Smooth Complexes
PROCEEDINGS OF THE EIGHTEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 2007, p. 1096-1105
Cheng, Siu-Wing; Dey, Tamal K.; Ramos, Edgar A.
Querying approximate shortest paths in anisotropic regions
Proceedings of the Annual Symposium on Computational Geometry, 2007, p. 84-91
Cheng, S.W.; Na, H.S.; Vigneron, A.; Wang, Y.


Expand All Collapse All


Article 3

Casting with skewed ejection direction
Algorithmica, v. 44, (4), 2006, May, p. 325-342
Ahn, HK; Cheng, SW; Cheong, O.
On the sizes of Delaunay meshes
COMPUTATIONAL geometry-theory and APPLICATIONS, v. 33, (3), 2006, FEB, p. 130-138
Cheng, SW
Three-dimensional Delaunay mesh generation
Discrete & Computational Geometry, v. 36, (3), 2006, OCT, p. 419-456
Cheng, Siu-Wing; Poon, Sheung-Hung

Conference paper 1

Anisotropic surface meshing
Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, 2006, p. 202-211
Cheng, S.W.; Dey, T.K.; Ramos, E.A.; Wenger, R.


Expand All Collapse All


Article 4

Casting an Object with a Core
Lecture Notes in Computer Science, v. 3827, 2005, p. 40-49
Ahn, HK; Bae, SW; Cheng, SW; Chwa, KY
Curve reconstruction from noisy samples
COMPUTATIONAL geometry-theory and APPLICATIONS, v. 31, (1-2), 2005, MAY, p. 63-100
Cheng, SW; Funke, S.; Golin, M.; Kumar, P.; Poon, SH; Ramos, E.
Energy efficient broadcasting and multicasting in static wireless ad hoc networks
Lecture Notes in Computer Science, v. 3521, 2005, p. 16-25
Cheng, SW; Jia, XH; Hung, F.; Wang, YJ
Quality meshing of polyhedra with small angles
International journal of computational geometry & applications, v. 15, (4), 2005, AUG, p. 421-461
Cheng, SW; Dey, TK; Ramos, EA; Ray, T.

Book chapter 1

Planar Straight Line Graphs
Handbook of Data Structures and Applications / Edited by Dinesh P. Mehta, Sartaj Sahni. Boca Raton, Fla.: Chapman & Hall/CRC, 2005, p. 17-1 - 17-17
Cheng, Siu-Wing

Conference paper 3

Manifold reconstruction from point samples
Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, 2005, p. 1018-1027
Cheng, S.W.; Dey, T.K.; Ramos, E.A.
Provable dimension detection using principal component analysis
Proceedings of the Annual Symposium on Computational Geometry, 2005, p. 208-217
Cheng, S.W.; Wang, Y.; Wu, Z.
Weighted Delaunay refinement for polyhedra with small angles
PROCEEDINGS OF THE 14TH INTERNATIONAL MESHING ROUNDTABLE, 2005, p. 325-342
Cheng, SW; Dey, TK; Ray, T.


Expand All Collapse All


Article 4

Competitive facility location: the Voronoi game
Theoretical Computer Science, v. 310, (1-3), 2004, JAN 1, p. 457-467
Ahn, HK; Cheng, SW; Cheong, O.; Golin, M.; van Oostrum, R.
Hierarchical decompositions and circular ray shooting in simple polygons
Discrete & Computational Geometry, v. 32, (3), 2004, OCT, p. 401-415
Cheng, SW; Cheong, O.; Everett, H.; van Oostrum, R.
Hierarchy of surface models and irreducible triangulations
Computational Geometry: Theory and Applications, v. 27, (2), 2004, Feb, p. 135-150
Cheng, Siu Wing; Dey, Tamal K.; Poon, Sheung-Hung
The reflex-free hull
International journal of computational geometry & applications, v. 14, (6), 2004, DEC, p. 453-474
Ahn, HK; Cheng, SW; Cheong, O.; Snoeyink, J.

Conference paper 3

On the Sizes of Delaunay Meshes
Proceedings of the International Symposium on Voronoi Diagrams in Science and Engineering, 2004, 104-113
Cheng, Siu-Wing
Quality meshing for polyhedra with small angles
Proceedings of the Annual Symposium on Computational Geometry, 2004, p. 290-299
Cheng, S.W.; Dey, T.K.; Ramos, E.A.; Ray, T.
Sampling and meshing a surface with guaranteed topology and geometry
Proceedings of the Annual Symposium on Computational Geometry, 2004, p. 280-289
Cheng, S.W.; Dey, T.K.; Ramos, E.A.; Ray, T.


Expand All Collapse All


Article 1

Quality meshing with weighted delaunay refinement
SIAM journal on computing, v. 33, (1), 2003, p. 69-93
Cheng, SW; Dey, TK

Conference paper 2

Curve reconstruction from noisy samples
Proceedings of the Annual Symposium on Computational Geometry, 2003, p. 302-311
Cheng, S.W.; Funke, S.; Golin, M.; Kumar, P.; Poon, S.H.; Ramos, E.
Graded conforming delaunay tetrahedralization with bounded radius-edge ratio
Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, 2003, p. 295-304
Cheng, S.W.; Poon, S.H.


Expand All Collapse All


Article 3

Hierarchy of surface models and irreducible triangulations
Lecture Notes in Computer Science, v. 2518, 2002, p. 286-295
Cheng, SW; Dey, TK; Poon, SH
Quadtree, ray shooting and approximate minimum weight Steiner triangulation
COMPUTATIONAL geometry-theory and APPLICATIONS, v. 23, (2), 2002, SEP, p. 99-116
Cheng, Siu Wing; Lee, Kamhing
Separating an object from its cast
Computer-Aided Design, v. 34, (8), 2002, JUL, p. 547-559
Ahn, HK; de Berg, M.; Bose, P.; Cheng, SW; Halperin, D.; Matousek, J.; Schwarzkopf, O.

Conference paper 3

Hierarchy of Surface Models and Irreducible Triangulation
Proceedings of the 13th International Symposium on Algorithms and Computation, 286-295
Cheng, Siu-Wing; Dey, Tamal K.; Poon, Sheung-Hung
Motorcycle graphs and straight skeletons
PROCEEDINGS OF THE THIRTEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 2002, p. 156-165
Cheng, SW; Vigneron, A.
Quality meshing with weighted Delaunay refinement
PROCEEDINGS OF THE THIRTEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 2002, p. 137-146
Cheng, SW; Dey, TK


Expand All Collapse All


Article 4

Approximation algorithm for multiple-tool milling
International journal of computational geometry & applications, v. 11, (3), 2001, JUN, p. 339-372
Arya, Sunil; Cheng, SW; Mount, DM
Competitive facility location along a highway
Lecture Notes in Computer Science, v. 2108, 2001, p. 237-246
Ahn, HK; Cheng, SW; Cheong, O.; Golin, M.; van Ostrum, R.
Design and analysis of planar shape deformation
COMPUTATIONAL geometry-theory and APPLICATIONS, v. 19, (2-3), 2001, JUL, p. 205-218
Cheng, SW; Edelsbrunner, H.; Fu, P.; Lam, KP
On β-skeleton as a subgraph of the minimum weight triangulation
Theoretical Computer Science, v. 262, (1-2), 2001, JUL 6, p. 459-471
Cheng, SW; Xu, XF

Conference paper 1

Competitive facility location: the Voronoi game
Computing and Combinatorics, Proc 7th Annual International Conference (COCOON 2001), v. 2108, 2001, p. 237-246
van Oostrum, R.; Ahn, Hee-Kap; Cheng, Siu Wing; Cheong, O.; Golin, Mordecai Jay


Expand All Collapse All


Article 4

Efficient Expected-Case Algorithms for Planar Point Location
Lecture Notes in Computer Science, v. 1851, 2000, p. 353-366
Arya, Sunil; Cheng, Siu-Wing; Mount, David M.; Ramesh, H.
LMT-skeleton heuristics for several new classes of optimal triangulations
COMPUTATIONAL geometry-theory and APPLICATIONS, v. 17, (1-2), 2000, OCT, p. 51-68
Dai, Yang; Katoh, Naoki; Cheng, Siu-Wing
Sliver exudation
Journal of the ACM, v. 47, (5), 2000, SEP, p. 883-904
Cheng, Siu-Wing; Dey, Tamal K.; Edelsbrunner, Herbert; Facello, Michael A.; Teng, Shang-Hua
The Steiner tree problem for terminals on the boundary of a rectilinear polygon
Theoretical Computer Science, v. 237, (1-2), 2000, APR 28, p. 213-238
Cheng, SW

Book chapter 1

Exact Steiner Trees in Graphs and Grid Graphs
Advances in Steiner Trees Combinatorial Optimization Volume 6 / Du Ding-Zhu, Smith JM, Rubinstein JH. US: Springer US, 2000, p. 137-162
Cheng, Siu Wing


Expand All Collapse All


Article 3

A triangulation for optimal strip decomposition in simple polygons
The second ACM Hong Kong postgraduate research day, 1999
Cheng, Siu Wing; Cheong, Jae-Sook
Hierachical Vertical Decompositions, Ray Shooting, and Circular Arc Queries in Simple Polygons
SCG 99' Proceedings of the 15th Annual ACM Symposium on Computational Geometry, 227-236
Cheng, Siu-Wing; Everett, Hazel; Cheong, Otfried; Oostrum, Rene Van
Improved constructions of Delaunay based contour surfaces
Proceedings of the Symposium on Solid Modeling and Applications, 1999, p. 322-323
Cheng, Siu-Wing; Dey, Tamal K.

Conference paper 5

Approximate minimum weight Steiner triangulation in three dimensions
Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, 1999, p. 205-214
Cheng, Siu-Wing; Dey, Tamal K.
Casting with skewed ejection direction revisited
CCCG, 1999
Ahn, Hee-Kap; Chen, Siu Wing; Cheong, Otfried
Hierarchical vertical decompositions, ray shooting, and circular arc queries in simple polygons
PROC ANNU SYMP COMPUT GEOM, pp. 227-236. 1999
Cheng, Siu-Wing; Everett, Hazel; Cheong, Otfried; van Oostrum, Rene
Hierarchical vertical decompositions, ray shooting, and circular arc queries in simple polygons
Proceedings of the fifteenth annual symposium on Computational geometry; 13-16 June 1999
Cheng, Siu-Wing; Everett, Hazel; Cheong, Otfried; van Oostrum, Rene
Sliver Exudation
Proceedings of the Annual Symposium on Computational Geometry, 1999, p. 1-13
Cheng, Siu-Wing; Dey, Tamal Krishna; Edelsbrunner, Herbert; Facello, Michael A.; Teng, Shang-Hua


Expand All Collapse All


Article 2

Minimum dominating sets of intervals on lines
Algorithmica (New York), v. 20, (3), 1998, p. 294-308
Cheng, Siu Wing; Kaminski, Michael; Zaks, Shmuel
Quadtree decomposition, Steiner triangulation, and ray shooting
Lecture Notes in Computer Science, v. 1533, 1998, p. 367-376
Cheng, SW; Lee, KH

Conference paper 3

Approximation algorithms for multiple-tool miling
Proceedings of the fourteenth annual symposium on Computational geometry, 07-10 June 1998, p. 297-306
Arya, Sunil; Cheng, Siu Wing; Mount, David M.
Casting with Skewed Ejection Direction
Lecture Notes in Computer Science, v. 1533 LNCS, 1998, p. 139-150
Ahn, Heekap; Cheng, Siu Wing; Cheong, Otfried
Design and analysis of planar shape deformation
Proceedings of the fourteenth annual symposium on Computational geometry, 7-10 June 1998, p. 29-38
Cheng, Siu-Wing; Edelsbrunner, Herbert; Fu, Ping; Lam, Ka-Po


Expand All Collapse All


Conference paper 1

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


Expand All Collapse All


Article 2

Triangulations intersect nicely
Discrete & Computational Geometry, v. 16, (4), 1996, DEC, p. 339-359
Aichholzer, O.; Aurenhammer, F.; Cheng, SW; Katoh, N.; Rote, G.; Taschwer, M.; Xu, YF
Widest empty L-shaped corridor
Information Processing Letters, v. 58, (6), 1996, JUN 24, p. 277-283
Cheng, SW

Conference paper 3

A Study of the LMT-Skeleton
Lecture Notes in Computer Science, v. 1178, 1996, p. 256-265
Cheng, Siu Wing; Katoh, Naoki; Sugai, Manabu
Approaching the largest β-skeleton within a minimum weight triangulation
Proceedings of the Annual Symposium on Computational Geometry, 1996, p. 196-203
Cheng, Siu-Wing; Xu, Yin-Feng
Isomorphism testing and display of symmetries in dynamic trees
PROCEEDINGS OF THE SEVENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 1996, p. 202-211
Cheng, SW; Ng, MP


Expand All Collapse All


Article 2

Constrained Independence System and Triangulations of Planar Point Sets
Lecture Notes in Computer Science, v. 959, 1995, p. 41-50
Cheng, Siu Wing; Xu, Yinfeng
Minimum Dominating Sets of Intervals on Lines
Lecture Notes in Computer Science, v. 959, 1995, p. 520-529
Cheng, Siu Wing; Kaminski, Michael; Zaks, Shmuel

Book chapter 1

A Fast Algorithm for Computing Optimal Rectilinear Steiner Trees for External Point Sets
Lecture Notes in Computer Science4 / v. 1004, 1995, p. 322-331
Cheng, Siu Wing; Tang, Chi Keung

Conference paper 2

A Fast Algorithm for Computing Optimal Rectilinear Steiner Trees for Extremal Point Sets
Proc. International Symposium on Algorithm and Computation, December 1995
Cheng, Siu Wing; Tang, Chi Keung
Expected case analysis of-skeletons with applications to the construction of minimum weight triangulations
Proc. 7th Canad. Conf. Comput. Geom, 1995, p. 279-284
Cheng, Siu Wing; Golin, Mordecai J.; Tsang, Jeffrey CF


Expand All Collapse All


Article 2

Modifications of Competitive Group Testing
SIAM Journal on Computing, v. 23, 1994, p. 82-96
Du, Ding-Zhu; Xue, Guo-Liang; Sun, Shang-Zhi; Cheng, Siu Wing
The Role of Long and Short Paths in Circuit Performance Optimization
IEEE Transactions on Computer-Aided Design, v. 13, 1994, p. 857-864
Cheng, Siu Wing; Chen, Hsi-Chuan; Du, David H.C.; Lim, Andrew


Expand All Collapse All


Article 3

Optimal Joining of Compacted Cells
IEEE Transactions on Computers, v. 42, 1993, p. 597-607
Lim, Andrew; Cheng, Siu Wing; Sahni, Sartaj
Performance Oriented Rectilinear Steiner Trees
Eletrik, v. 1, 1993, p. 137-152
Lim, Andrew; Cheng, Siu Wing; Wu, Ching-Ting
SINGLE JOG MINIMUM AREA JOINING OF COMPACTED CELLS
Information Processing Letters, v. 47, (4), 1993, SEP 27, p. 167-172
LIM, A.; CHEE, YM; CHENG, SW

Conference paper 3

A Path Sensitization Approach to Area Optimization
Proceedings of IEEE International Conference on Computer Design: VLSI in Computers and Processors, 1993, p. 73-76
Chen, Hsi-Chuan; Cheng, Siu Wing; Hsu, Yaun-Chung; Du, David H.C.
Optimal Rectilinear Steiner Tree for Extremal Point Sets
Proceedings of the 4th Annual Symposium on Algorithms and Computation (ISAAC), 1993, p. 523-532
Cheng, Siu Wing; Lim, Andrew; Wu, Ching-Ting
Performance Oriented Rectilinear Steiner Trees
Proceedings of the 30th Design Automation Conference (DAC), 1993, p. 171-176
Lim, Andrew; Cheng, Siu Wing; Wu, Ching-Ting


Expand All Collapse All


Article 3

Algorithms for Ray-Shooting and Intersection Searching
Journal of Algorithms, v. 13, 1992, p. 670-692
Cheng, Siu Wing; Janardan, Ravi
Efficient Distributed Algorithms for Single-Source Shortest Paths and Related Problems on Plane Networks
Mathematical Systems Theory, v. 25, 1992, p. 93-122
Janardan, Ravi; Cheng, Siu Wing
New Results on Dynamic Planar Point Location
SIAM Journal on Computing, v. 21, 1992, p. 972-999
Cheng, Siu Wing; Janardan, Ravi

Conference paper 3

Circuit enhancement by eliminating long false paths
Proceedings of the 29th Design Automation Conference (DAC), 1992, p. 249-252
Chen, Hsi-Chuan; Du, David H.C.; Cheng, Siu Wing
Optimal Joining of Compacted Cells
Proceedings of the 1992 Brown/MIT Conference on Advanced Research in VLSI and Parallel Systems, 1992, p. 99-112
Lim, Andrew; Cheng, Siu Wing; Sahni, Sartaj
The Role of Long and Short Paths in Circuit Performance Optimization
Proceedings of the 29th Design Automation Conference (DAC), 1992, p. 543-548
Cheng, Siu Wing; Chen, Hsi-Chuan; Du, David H.C.; Lim, Andrew


Expand All Collapse All


Article 1

Efficient Maintenance of the Union of Intervals on a Line, with Applications
Journal of Algorithms, v. 12, 1991, p. 57-74
Cheng, Siu Wing; Janardan, Ravi

Conference paper 1

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


Expand All Collapse All


Article 1

Efficient Dynamic Algorithms for some Geometric Intersection Problems
Information Processing Letters, v. 36, 1990, p. 251-258
Cheng, Siu Wing; Janardan, Ravi

Conference paper 2

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, p. 74-83
Cheng, Siu Wing; Janardan, Ravi
New results on Dynamic Planar Point Location
Proceedings of the 31st Annual IEEE Symposium on Foundations of Computer Science (FOCS), 1990, p. 96-105
Cheng, Siu Wing; Janardan, Ravi


Expand All Collapse All


2016 7

A Faster Algorithm for Computing Straight Skeletons
ACM transactions on algorithms, v. 12, (3), June 2016, Article number 44
Cheng, Siu Wing; Liam, Mencel; Antoine, Vigneron Article
Tangent Estimation from Point Samples
Discrete and Computational Geometry, v. 56, (3), October 2016, p. 505-557
Cheng, Siu Wing; Chiu, Man Kwun Article
3D conforming delaunay triangulation
Encyclopedia of algorithms (2nd ed.) / Edited by Ming-Yang Kao. New York, NY : Springer New York, 2016, p. 499-502
Cheng, Siu-Wing Book chapter
Delaunay Mesh Generation
Delaunay Mesh Generation / Editor(s): Cheng, Siu Wing, Dey, Tamal K. and Shewchuk, Jonathan. CRC Press, 2016, p. 1-386
Cheng, Siu Wing; Dey, Tamal K.; Shewchuk, Jonathan Book chapter
Manifold reconstruction
Encyclopedia of algorithms (2nd ed.) / Edited by Ming-Yang Kao. New York, NY : Springer New York, 2016, p. 1185-1189
Cheng, Siu-Wing Book chapter
Approximating convex shapes with respect to symmetric difference under homotheties
Leibniz International Proceedings in Informatics, LIPIcs, v. 51, 2016, p. 63.1-63.15
Yon, Juyoung; Bae, Sang Won; Cheng, Siu Wing; Cheong, Otfried; Wilkinson, Bryan T. Conference paper
Minimax Regret 1-Median Problem in Dynamic Path Networks
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), v. 9843, 2016, p. 122-134
Higashikawa, Yuya; Cheng, Siu-Wing; Kameda, Tsunehiko; Katoh, Naoki; Saburi, Shun Conference paper

2015 7

Edge Flips in Surface Meshes
Discrete and Computational Geometry, v. 54, (1), July 2015, p. 110-151
Cheng, Siu-Wing; Jin, Jiongxin Article
Minimax regret 1-sink location problem in dynamic path networks
Theoretical Computer Science, v. 588, July 2015, p. 24-36
Higashikawa, Yuya; Augustine, John; Cheng, Siu-Wing; Golin, Mordecai Jay; Katoh, Naoki; Ni, Guanqun; Su, Bing; Xu, Yinfeng Article
Adaptive Point Location in Planar Convex Subdivisions
Lecture Notes in Computer Science, v. 9472, 2015, p. 14-22
Cheng, Siu Wing; Lau, Man Kit Conference paper
Deforming Surface Meshes
SEMA SIMAI Springer Series, v. 5, 2015, p. 69-89
Cheng, Siu Wing; Jin, Jiongxin Conference paper
Navigating Weighted Regions With Scattered Skinny Tetrahedra
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), v. 9472, 2015, p. 35-45
Cheng, Siu Wing; Chiu, Mankwun; Jin, Jiongxin; Vigneron, Antoine Conference paper
Piecewise Linear Approximation of Streaming Time Series Data with Max-error Guarantees
2015 IEEE 31st International Conference on Data Engineering (ICDE 2015), Institute of Electrical and Electronics Engineers (IEEE), 2015, p. 173-184
Luo, Ge; Yi, Ke; Cheng, Siu-Wing; Li, Zhenguo; Fan, Wei; He, Cheng; Mu, Yadong Conference paper
Triangulation Refinement and Approximate Shortest Paths in Weighted Regions
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, The Society for Industrial and Applied Mathematics (SIAM), 2015, p. 1626-1640
Cheng, Siu-Wing; Jin, Jiongxin; Antoine, Vigneron Conference paper

2014 7

Approximate Shortest Descending Paths
SIAM journal on computing, v. 43, (2), January 2014, p. 410-428
Cheng, Siu Wing; Jin, Jiongxin Article
Overlap of convex polytopes under rigid motion
Computational Geometry: Theory and Applications, v. 47, (1), 2014, p. 15-24
Ahn, Hee-Kap; Cheng, Siu-Wing; Kweon, Hyuk Jun; Yon, Juyoung Article
3D Conforming Delaunay Triangulation
Encyclopedia of Algorithms / Editor: Ming Yang Kao. New York : Springer Science, Business Media New York, 2014, p. 1-5
Cheng, Siu Wing Book chapter
Manifold Reconstruction
Encyclopedia of Algorithms / Editor: Ming Yang Kao. New York : Springer Science, Business Media New York, 2014, p. 1-6
Cheng, Siu Wing Book chapter
A Faster Algorithm for Computing Straight Skeletons
Lecture Notes in Computer Science, v. 8737 LNCS, 2014, p. 272-283
Cheng, Siuwing; Liam, Mencel; Antoine, Vigneron Conference paper
Implicit Manifold Reconstruction
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2014, p. 161-173
Cheng, Siu Wing; Chiu, Man Kwun Conference paper
Shortest Paths on Polyhedral Surfaces and Terrains
Proceedings of the forty-sixth annual ACM symposium on Theory of computing, New York, NY, USA : ACM, 2014, p. 373-382
Cheng, Siu Wing; Jin, Jiongxin Conference paper

2013 6

Maximum Overlap of Convex Polytopes under Translation
Computational Geometry: Theory and Applications, v. 46, (5), July 2013, p. 552-565
Ahn, Hee-Kap; Cheng, Siu-Wing; Reinbacher, Iris Article
Shape matching under rigid motion
Computational Geometry: Theory and Applications, v. 46, (6), 2013, p. 591-603
Cheng, Siu Wing; Lam, Chi Kit Article
Delaunay Mesh Generation
Delaunay Mesh Generation / By Siu-Wing Cheng, Tamal Krishna Dey, Jonathan Richard Shewchuk
Cheng, Siu Wing; Dey, Tamal Krishna; Shewchuk, Jonathan Richard Book
Algorithms and Computation
Lecture Notes in Computer Science LNCS, v. 8283
Cai, Leizhen; Cheng, Siu Wing; Lam, Tak Wah Conference paper
Approximate Shortest Descending Path
Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, v. 2013, 2013, p. 144-155
Cheng, Siu Wing; Jin, Jiongxin Conference paper
Minimax Regret 1-Sink Location Problems in Dynamic Path Networks
Theory and Applications of Models of Computation, 10th International Conference, TAMC 2013: Proceedings, Editors: T-H. Hubert Chan, Lap Chi Lau, Luca Trevisan. Berlin; Heidelberg : Springer-Verlag, 2013, p. 121-132, Part of the Lecture Notes in Computer Science book series (LNCS, volume 7876)
Cheng, Siu-Wing; Higashikawa, Yuya; Katoh, Naoki; Ni, Guanqun; Su, Bing; Xu, Yinfeng Conference paper

2012 4

Approximate Shortest Homotopic Paths in Weighted Regions
International Journal of Computational Geometry & Applications, v. 22, February 2012, p. 83-102
Cheng, Siu-Wing; Jin, Jiongxin; Vigneron, Antoine; Wang, Yajun Article
Range Searching on Uncertain Data
ACM transactions on algorithms, v. 8, (4), September 2012, Article 43
Agarwal, Pankaj K.; Cheng, Siu-Wing; Yi, Ke Article
A fast and simple surface reconstruction algorithm
Symposium on Computational Geometry 2012, University of North Carolina at Chapel Hill, June 2012, p. 69-78
Cheng, Siu Wing; Jin, Jiongxin; Lau, Man Kit Conference paper
Overlap of convex polytopes under rigid motion
Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), Hyderabad, India, Dec 15-17 2012, p. 498-509
Ahn, H.K.; Cheng, S.W.; Kweon, H.J.; Yon, J. Conference paper

2011 1

Edge Flips and Deforming Surface Meshes
COMPUTATIONAL GEOMETRY (SCG 11), 2011, p. 331-340
Cheng, Siu-Wing; Jin, Jiongxin Conference paper

2010 6

Delaunay Refinement for Piecewise Smooth Complexes
Discrete & Computational Geometry, v. 43, (1), 2010, JAN, p. 121-166
Cheng, Siu-Wing; Dey, Tamal K.; Ramos, Edgar A. Article
Querying Approximate Shortest Paths in Anisotropic Regions
SIAM Journal on Computing, v. 39, (5), 2010, p. 1888-1918
Cheng, Siu-Wing; Na, Hyeon-Suk; Vigneron, Antoine; Wang, Yajun Article
Approximate Homotopic Shortest Paths in Anisotropic Regions
International Symposium on Algorithms and Computation, Jeju, Korea, December 15-17, 2010, Lecture Notes in Computer Science 6507, pages 109-120
Cheng, Siu-Wing; Jin, Jiongxin; Vigneron, Antoine; Wang, Yajun Conference paper
Approximate shortest homotopic paths in weighted regions
Lecture Notes in Computer Science, v. 6507, (PART 2), 2010, p. 109-120
Cheng, S.W.; Jin, J.; Vigneron, A.; Wang, Y. Conference paper
Approximating the Average Stretch Factor of Geometric Graphs
Lecture Notes in Computer Science, v. 6506, 2010, p. 37-48
Cheng, Siu-Wing; Knauer, Christian; Langerman, Stefan; Smid, Michiel Conference paper
Maximum overlap of convex polytopes under translation
Lecture Notes in Computer Science, v. 6507, (PART 2), 2010, p. 97-108
Ahn, H.K.; Cheng, S.W.; Reinbacher, I. Conference paper

2009 5

Advances in Surface Meshing
数理解析研究所講究録, v. 1641, 2009, p. 125-134
Cheng, Siu Wing Article
Casting an Object with a Core
Algorithmica, v. 54, (1), 2009, MAY, p. 72-88
Ahn, Hee-Kap; Bae, Sang Won; Cheng, Siu-Wing; Chwa, Kyung-Yong Article
Dimension detection via slivers
Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, 4-6 January 2009, p. 1001-1010
Cheng, S.W.; Chiu, M.K. Conference paper
Indexing uncertain data
Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2009, p. 137-146
Agarwal, P.K.; Cheng, S.W.; Tao, Y.; Yi, K. Conference paper
Theory of a Practical Delaunay Meshing Algorithm for a Large Class of Domains
ALGORITHMS, ARCHITECTURES AND INFORMATION SYSTEMS SECURITY, v. 3, 2009, p. 25-42
Cheng, Siu-Wing; Dey, Tamal K.; Levine, Joshua Conference paper

2008 4

Approximate shortest paths in anisotropic regions
SIAM journal on computing, v. 38, (3), 2008, p. 802-824
Cheng, Siu-Wing; Na, Hyeon-Suk; Vigneron, Antoine; Wang, Yajun Article
PROVABLE DIMENSION DETECTION USING PRINCIPAL COMPONENT ANALYSIS
International journal of computational geometry & applications, v. 18, (5), 2008, OCT, p. 415-440
Cheng, Siu-Wing; Wang, Yajun; Wu, Zhaungzhi Article
A practical Delaunay meshing algorithm for a large class of domains
Proceedings of the 16th International Meshing Roundtable, 2008, p. 477-494
Cheng, Siu-Wing; Dev, Tamal K.; Levine, Joshua A. Conference paper
Maintaining deforming surface meshes
Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, 2008, p. 112-121
Cheng, S.W.; Dey, T.K. Conference paper

2007 5

Motorcycle graphs and straight skeletons
Algorithmica, v. 47, (2), 2007, FEB, p. 159-182
Cheng, Siu-Wing; Vigneron, Antoine Article
Sampling and meshing a surface with guaranteed topology and geometry
SIAM journal on computing, v. 37, (4), 2007, Sep, p. 1199-1227
Cheng, Siu-Wing; Dey, Tamal K.; Ramos, Edgar A.; Ray, Tathagata Article
Approximate shortest paths in anisotropic regions
Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, 2007, p. 766-774
Cheng, Siu-Wing; Na, Hyeon-Suk; Vigneron, Antoine; Wang, Yajun Conference paper
Delaunay Refinement for Piecewise Smooth Complexes
PROCEEDINGS OF THE EIGHTEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 2007, p. 1096-1105
Cheng, Siu-Wing; Dey, Tamal K.; Ramos, Edgar A. Conference paper
Querying approximate shortest paths in anisotropic regions
Proceedings of the Annual Symposium on Computational Geometry, 2007, p. 84-91
Cheng, S.W.; Na, H.S.; Vigneron, A.; Wang, Y. Conference paper

2006 4

Casting with skewed ejection direction
Algorithmica, v. 44, (4), 2006, May, p. 325-342
Ahn, HK; Cheng, SW; Cheong, O. Article
On the sizes of Delaunay meshes
COMPUTATIONAL geometry-theory and APPLICATIONS, v. 33, (3), 2006, FEB, p. 130-138
Cheng, SW Article
Three-dimensional Delaunay mesh generation
Discrete & Computational Geometry, v. 36, (3), 2006, OCT, p. 419-456
Cheng, Siu-Wing; Poon, Sheung-Hung Article
Anisotropic surface meshing
Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, 2006, p. 202-211
Cheng, S.W.; Dey, T.K.; Ramos, E.A.; Wenger, R. Conference paper

2005 8

Casting an Object with a Core
Lecture Notes in Computer Science, v. 3827, 2005, p. 40-49
Ahn, HK; Bae, SW; Cheng, SW; Chwa, KY Article
Curve reconstruction from noisy samples
COMPUTATIONAL geometry-theory and APPLICATIONS, v. 31, (1-2), 2005, MAY, p. 63-100
Cheng, SW; Funke, S.; Golin, M.; Kumar, P.; Poon, SH; Ramos, E. Article
Energy efficient broadcasting and multicasting in static wireless ad hoc networks
Lecture Notes in Computer Science, v. 3521, 2005, p. 16-25
Cheng, SW; Jia, XH; Hung, F.; Wang, YJ Article
Quality meshing of polyhedra with small angles
International journal of computational geometry & applications, v. 15, (4), 2005, AUG, p. 421-461
Cheng, SW; Dey, TK; Ramos, EA; Ray, T. Article
Planar Straight Line Graphs
Handbook of Data Structures and Applications / Edited by Dinesh P. Mehta, Sartaj Sahni. Boca Raton, Fla.: Chapman & Hall/CRC, 2005, p. 17-1 - 17-17
Cheng, Siu-Wing Book chapter
Manifold reconstruction from point samples
Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, 2005, p. 1018-1027
Cheng, S.W.; Dey, T.K.; Ramos, E.A. Conference paper
Provable dimension detection using principal component analysis
Proceedings of the Annual Symposium on Computational Geometry, 2005, p. 208-217
Cheng, S.W.; Wang, Y.; Wu, Z. Conference paper
Weighted Delaunay refinement for polyhedra with small angles
PROCEEDINGS OF THE 14TH INTERNATIONAL MESHING ROUNDTABLE, 2005, p. 325-342
Cheng, SW; Dey, TK; Ray, T. Conference paper

2004 7

Competitive facility location: the Voronoi game
Theoretical Computer Science, v. 310, (1-3), 2004, JAN 1, p. 457-467
Ahn, HK; Cheng, SW; Cheong, O.; Golin, M.; van Oostrum, R. Article
Hierarchical decompositions and circular ray shooting in simple polygons
Discrete & Computational Geometry, v. 32, (3), 2004, OCT, p. 401-415
Cheng, SW; Cheong, O.; Everett, H.; van Oostrum, R. Article
Hierarchy of surface models and irreducible triangulations
Computational Geometry: Theory and Applications, v. 27, (2), 2004, Feb, p. 135-150
Cheng, Siu Wing; Dey, Tamal K.; Poon, Sheung-Hung Article
The reflex-free hull
International journal of computational geometry & applications, v. 14, (6), 2004, DEC, p. 453-474
Ahn, HK; Cheng, SW; Cheong, O.; Snoeyink, J. Article
On the Sizes of Delaunay Meshes
Proceedings of the International Symposium on Voronoi Diagrams in Science and Engineering, 2004, 104-113
Cheng, Siu-Wing Conference paper
Quality meshing for polyhedra with small angles
Proceedings of the Annual Symposium on Computational Geometry, 2004, p. 290-299
Cheng, S.W.; Dey, T.K.; Ramos, E.A.; Ray, T. Conference paper
Sampling and meshing a surface with guaranteed topology and geometry
Proceedings of the Annual Symposium on Computational Geometry, 2004, p. 280-289
Cheng, S.W.; Dey, T.K.; Ramos, E.A.; Ray, T. Conference paper

2003 3

Quality meshing with weighted delaunay refinement
SIAM journal on computing, v. 33, (1), 2003, p. 69-93
Cheng, SW; Dey, TK Article
Curve reconstruction from noisy samples
Proceedings of the Annual Symposium on Computational Geometry, 2003, p. 302-311
Cheng, S.W.; Funke, S.; Golin, M.; Kumar, P.; Poon, S.H.; Ramos, E. Conference paper
Graded conforming delaunay tetrahedralization with bounded radius-edge ratio
Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, 2003, p. 295-304
Cheng, S.W.; Poon, S.H. Conference paper

2002 6

Hierarchy of surface models and irreducible triangulations
Lecture Notes in Computer Science, v. 2518, 2002, p. 286-295
Cheng, SW; Dey, TK; Poon, SH Article
Quadtree, ray shooting and approximate minimum weight Steiner triangulation
COMPUTATIONAL geometry-theory and APPLICATIONS, v. 23, (2), 2002, SEP, p. 99-116
Cheng, Siu Wing; Lee, Kamhing Article
Separating an object from its cast
Computer-Aided Design, v. 34, (8), 2002, JUL, p. 547-559
Ahn, HK; de Berg, M.; Bose, P.; Cheng, SW; Halperin, D.; Matousek, J.; Schwarzkopf, O. Article
Hierarchy of Surface Models and Irreducible Triangulation
Proceedings of the 13th International Symposium on Algorithms and Computation, 286-295
Cheng, Siu-Wing; Dey, Tamal K.; Poon, Sheung-Hung Conference paper
Motorcycle graphs and straight skeletons
PROCEEDINGS OF THE THIRTEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 2002, p. 156-165
Cheng, SW; Vigneron, A. Conference paper
Quality meshing with weighted Delaunay refinement
PROCEEDINGS OF THE THIRTEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 2002, p. 137-146
Cheng, SW; Dey, TK Conference paper

2001 5

Approximation algorithm for multiple-tool milling
International journal of computational geometry & applications, v. 11, (3), 2001, JUN, p. 339-372
Arya, Sunil; Cheng, SW; Mount, DM Article
Competitive facility location along a highway
Lecture Notes in Computer Science, v. 2108, 2001, p. 237-246
Ahn, HK; Cheng, SW; Cheong, O.; Golin, M.; van Ostrum, R. Article
Design and analysis of planar shape deformation
COMPUTATIONAL geometry-theory and APPLICATIONS, v. 19, (2-3), 2001, JUL, p. 205-218
Cheng, SW; Edelsbrunner, H.; Fu, P.; Lam, KP Article
On β-skeleton as a subgraph of the minimum weight triangulation
Theoretical Computer Science, v. 262, (1-2), 2001, JUL 6, p. 459-471
Cheng, SW; Xu, XF Article
Competitive facility location: the Voronoi game
Computing and Combinatorics, Proc 7th Annual International Conference (COCOON 2001), v. 2108, 2001, p. 237-246
van Oostrum, R.; Ahn, Hee-Kap; Cheng, Siu Wing; Cheong, O.; Golin, Mordecai Jay Conference paper

2000 5

Efficient Expected-Case Algorithms for Planar Point Location
Lecture Notes in Computer Science, v. 1851, 2000, p. 353-366
Arya, Sunil; Cheng, Siu-Wing; Mount, David M.; Ramesh, H. Article
LMT-skeleton heuristics for several new classes of optimal triangulations
COMPUTATIONAL geometry-theory and APPLICATIONS, v. 17, (1-2), 2000, OCT, p. 51-68
Dai, Yang; Katoh, Naoki; Cheng, Siu-Wing Article
Sliver exudation
Journal of the ACM, v. 47, (5), 2000, SEP, p. 883-904
Cheng, Siu-Wing; Dey, Tamal K.; Edelsbrunner, Herbert; Facello, Michael A.; Teng, Shang-Hua Article
The Steiner tree problem for terminals on the boundary of a rectilinear polygon
Theoretical Computer Science, v. 237, (1-2), 2000, APR 28, p. 213-238
Cheng, SW Article
Exact Steiner Trees in Graphs and Grid Graphs
Advances in Steiner Trees Combinatorial Optimization Volume 6 / Du Ding-Zhu, Smith JM, Rubinstein JH. US: Springer US, 2000, p. 137-162
Cheng, Siu Wing Book chapter

1999 8

A triangulation for optimal strip decomposition in simple polygons
The second ACM Hong Kong postgraduate research day, 1999
Cheng, Siu Wing; Cheong, Jae-Sook Article
Hierachical Vertical Decompositions, Ray Shooting, and Circular Arc Queries in Simple Polygons
SCG 99' Proceedings of the 15th Annual ACM Symposium on Computational Geometry, 227-236
Cheng, Siu-Wing; Everett, Hazel; Cheong, Otfried; Oostrum, Rene Van Article
Improved constructions of Delaunay based contour surfaces
Proceedings of the Symposium on Solid Modeling and Applications, 1999, p. 322-323
Cheng, Siu-Wing; Dey, Tamal K. Article
Approximate minimum weight Steiner triangulation in three dimensions
Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, 1999, p. 205-214
Cheng, Siu-Wing; Dey, Tamal K. Conference paper
Casting with skewed ejection direction revisited
CCCG, 1999
Ahn, Hee-Kap; Chen, Siu Wing; Cheong, Otfried Conference paper
Hierarchical vertical decompositions, ray shooting, and circular arc queries in simple polygons
PROC ANNU SYMP COMPUT GEOM, pp. 227-236. 1999
Cheng, Siu-Wing; Everett, Hazel; Cheong, Otfried; van Oostrum, Rene Conference paper
Hierarchical vertical decompositions, ray shooting, and circular arc queries in simple polygons
Proceedings of the fifteenth annual symposium on Computational geometry; 13-16 June 1999
Cheng, Siu-Wing; Everett, Hazel; Cheong, Otfried; van Oostrum, Rene Conference paper
Sliver Exudation
Proceedings of the Annual Symposium on Computational Geometry, 1999, p. 1-13
Cheng, Siu-Wing; Dey, Tamal Krishna; Edelsbrunner, Herbert; Facello, Michael A.; Teng, Shang-Hua Conference paper

1998 5

Minimum dominating sets of intervals on lines
Algorithmica (New York), v. 20, (3), 1998, p. 294-308
Cheng, Siu Wing; Kaminski, Michael; Zaks, Shmuel Article
Quadtree decomposition, Steiner triangulation, and ray shooting
Lecture Notes in Computer Science, v. 1533, 1998, p. 367-376
Cheng, SW; Lee, KH Article
Approximation algorithms for multiple-tool miling
Proceedings of the fourteenth annual symposium on Computational geometry, 07-10 June 1998, p. 297-306
Arya, Sunil; Cheng, Siu Wing; Mount, David M. Conference paper
Casting with Skewed Ejection Direction
Lecture Notes in Computer Science, v. 1533 LNCS, 1998, p. 139-150
Ahn, Heekap; Cheng, Siu Wing; Cheong, Otfried Conference paper
Design and analysis of planar shape deformation
Proceedings of the fourteenth annual symposium on Computational geometry, 7-10 June 1998, p. 29-38
Cheng, Siu-Wing; Edelsbrunner, Herbert; Fu, Ping; Lam, Ka-Po Conference paper

1997 1

Separating an Object from its Cast
Proceedings of the 13th Annual Symposium on Computational Geometry (SOCG), Nice, France, June 7-10 1997, p. 221-230
Ahn, Hee-Kap; Berg, Mark de; Bose, Prosenjit; Cheng, Siu-Wing; Halperin, Dan; Matousek, Jiri; Schwarzkopf, Otfried Conference paper

1996 5

Triangulations intersect nicely
Discrete & Computational Geometry, v. 16, (4), 1996, DEC, p. 339-359
Aichholzer, O.; Aurenhammer, F.; Cheng, SW; Katoh, N.; Rote, G.; Taschwer, M.; Xu, YF Article
Widest empty L-shaped corridor
Information Processing Letters, v. 58, (6), 1996, JUN 24, p. 277-283
Cheng, SW Article
A Study of the LMT-Skeleton
Lecture Notes in Computer Science, v. 1178, 1996, p. 256-265
Cheng, Siu Wing; Katoh, Naoki; Sugai, Manabu Conference paper
Approaching the largest β-skeleton within a minimum weight triangulation
Proceedings of the Annual Symposium on Computational Geometry, 1996, p. 196-203
Cheng, Siu-Wing; Xu, Yin-Feng Conference paper
Isomorphism testing and display of symmetries in dynamic trees
PROCEEDINGS OF THE SEVENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 1996, p. 202-211
Cheng, SW; Ng, MP Conference paper

1995 5

Constrained Independence System and Triangulations of Planar Point Sets
Lecture Notes in Computer Science, v. 959, 1995, p. 41-50
Cheng, Siu Wing; Xu, Yinfeng Article
Minimum Dominating Sets of Intervals on Lines
Lecture Notes in Computer Science, v. 959, 1995, p. 520-529
Cheng, Siu Wing; Kaminski, Michael; Zaks, Shmuel Article
A Fast Algorithm for Computing Optimal Rectilinear Steiner Trees for External Point Sets
Lecture Notes in Computer Science4 / v. 1004, 1995, p. 322-331
Cheng, Siu Wing; Tang, Chi Keung Book chapter
A Fast Algorithm for Computing Optimal Rectilinear Steiner Trees for Extremal Point Sets
Proc. International Symposium on Algorithm and Computation, December 1995
Cheng, Siu Wing; Tang, Chi Keung Conference paper
Expected case analysis of-skeletons with applications to the construction of minimum weight triangulations
Proc. 7th Canad. Conf. Comput. Geom, 1995, p. 279-284
Cheng, Siu Wing; Golin, Mordecai J.; Tsang, Jeffrey CF Conference paper

1994 2

Modifications of Competitive Group Testing
SIAM Journal on Computing, v. 23, 1994, p. 82-96
Du, Ding-Zhu; Xue, Guo-Liang; Sun, Shang-Zhi; Cheng, Siu Wing Article
The Role of Long and Short Paths in Circuit Performance Optimization
IEEE Transactions on Computer-Aided Design, v. 13, 1994, p. 857-864
Cheng, Siu Wing; Chen, Hsi-Chuan; Du, David H.C.; Lim, Andrew Article

1993 6

Optimal Joining of Compacted Cells
IEEE Transactions on Computers, v. 42, 1993, p. 597-607
Lim, Andrew; Cheng, Siu Wing; Sahni, Sartaj Article
Performance Oriented Rectilinear Steiner Trees
Eletrik, v. 1, 1993, p. 137-152
Lim, Andrew; Cheng, Siu Wing; Wu, Ching-Ting Article
SINGLE JOG MINIMUM AREA JOINING OF COMPACTED CELLS
Information Processing Letters, v. 47, (4), 1993, SEP 27, p. 167-172
LIM, A.; CHEE, YM; CHENG, SW Article
A Path Sensitization Approach to Area Optimization
Proceedings of IEEE International Conference on Computer Design: VLSI in Computers and Processors, 1993, p. 73-76
Chen, Hsi-Chuan; Cheng, Siu Wing; Hsu, Yaun-Chung; Du, David H.C. Conference paper
Optimal Rectilinear Steiner Tree for Extremal Point Sets
Proceedings of the 4th Annual Symposium on Algorithms and Computation (ISAAC), 1993, p. 523-532
Cheng, Siu Wing; Lim, Andrew; Wu, Ching-Ting Conference paper
Performance Oriented Rectilinear Steiner Trees
Proceedings of the 30th Design Automation Conference (DAC), 1993, p. 171-176
Lim, Andrew; Cheng, Siu Wing; Wu, Ching-Ting Conference paper

1992 6

Algorithms for Ray-Shooting and Intersection Searching
Journal of Algorithms, v. 13, 1992, p. 670-692
Cheng, Siu Wing; Janardan, Ravi Article
Efficient Distributed Algorithms for Single-Source Shortest Paths and Related Problems on Plane Networks
Mathematical Systems Theory, v. 25, 1992, p. 93-122
Janardan, Ravi; Cheng, Siu Wing Article
New Results on Dynamic Planar Point Location
SIAM Journal on Computing, v. 21, 1992, p. 972-999
Cheng, Siu Wing; Janardan, Ravi Article
Circuit enhancement by eliminating long false paths
Proceedings of the 29th Design Automation Conference (DAC), 1992, p. 249-252
Chen, Hsi-Chuan; Du, David H.C.; Cheng, Siu Wing Conference paper
Optimal Joining of Compacted Cells
Proceedings of the 1992 Brown/MIT Conference on Advanced Research in VLSI and Parallel Systems, 1992, p. 99-112
Lim, Andrew; Cheng, Siu Wing; Sahni, Sartaj Conference paper
The Role of Long and Short Paths in Circuit Performance Optimization
Proceedings of the 29th Design Automation Conference (DAC), 1992, p. 543-548
Cheng, Siu Wing; Chen, Hsi-Chuan; Du, David H.C.; Lim, Andrew Conference paper

1991 2

Efficient Maintenance of the Union of Intervals on a Line, with Applications
Journal of Algorithms, v. 12, 1991, p. 57-74
Cheng, Siu Wing; Janardan, Ravi Article
Space-Efficient Ray-Shooting and Intersection Searching: Algorithms, Dynamization, and Applications
Proceedings of the 2nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 1991, p. 7-16
Cheng, Siu Wing; Janardan, Ravi Conference paper

1990 3

Efficient Dynamic Algorithms for some Geometric Intersection Problems
Information Processing Letters, v. 36, 1990, p. 251-258
Cheng, Siu Wing; Janardan, Ravi Article
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, p. 74-83
Cheng, Siu Wing; Janardan, Ravi Conference paper
New results on Dynamic Planar Point Location
Proceedings of the 31st Annual IEEE Symposium on Foundations of Computer Science (FOCS), 1990, p. 96-105
Cheng, Siu Wing; Janardan, Ravi Conference paper


No Publications






Teaching Assignment

---

2021-22 Winter 0 2021-22 Fall 5 2020-21 Summer 0 2020-21 Spring 3 2020-21 Winter 1 2020-21 Fall 3

---

COMP3711 Design and Analysis of Algorithms
COMP4981 Final Year Project
CSIT5500 Advanced Algorithms
RMBI4980 Risk Management and Business Intelligence Capstone Project I
UROP1100E Undergraduate Research Opportunities Series 1


COMP5713 Computational Geometry
CSIT5500 Advanced Algorithms
RMBI4990 Risk Management and Business Intelligence Capstone Project II


COMP4971A Independent Work


COMP3711 Design and Analysis of Algorithms
COMP4971C Independent Work
RMBI4980 Risk Management and Business Intelligence Capstone Project I


No Teaching Assignments


No Teaching Assignments






Research Postgraduate (RPG) Supervision From January 2019 to December 2022 (As of 30 January 2022)

---

All Supervisions Current RPGs Graduated RPGs

---

Current RPGs

---

Doctor of Philosophy WANG, Zhe (co-supervision)
Computer Science and Engineering( 2021 - )

HUANG, Haoqiang
Computer Science and Engineering( 2020 - )

LEE, Taegyoung
Computer Science and Engineering( 2019 - )

WONG, Man Ting
Computer Science and Engineering( 2018 - )

---

Graduated RPGs

---

Doctor of Philosophy LAU, Man Kit
Computer Science and Engineering( Completed in 2020 )

MAO, Yuchen
Computer Science and Engineering( Completed in 2019 )









ProjectsFrom January 2020 to December 2022

---

All Projects 4

---

No Projects.
Max-Min Allocation of Indivisible Resources


不可分割資源的最小最大化分配 Leading


RGC - General Research Fund


Project Team (HKUST)
CHENG Siu Wing (Lead)


2020 -




Proximity Graph Construction


建造鄰近圖 Leading


RGC - General Research Fund


Project Team (HKUST)
CHENG Siu Wing (Lead)


2019 -




Design and Analysis of Self-Improving Algorithms


自我改進算法的設計與分析 Leading


RGC - General Research Fund


Project Team (HKUST)
CHENG Siu Wing (Lead)


2018 - 2021




Distribution-Sensitive and Distribution-Adaptive Planar Point Location


適應分佈和分佈敏感的平面定點方法 Leading


RGC - General Research Fund


Project Team (HKUST)
CHENG Siu Wing (Lead)


2017 - 2020