The Discrete and Computational Geometry Laboratory is formed
by Otfried Cheong
and his graduate students and postdocs.
You can find all of us in room 3433 in the Computer Science
Building (E3-1), or call us at extension 7742.
We do research in two related areas:
- Computational Geometry
Computational Geometry is the area of computer science
that studies efficient algorithms for geometric problems. The
problems studied come from applications in graphics, CAD,
robotics, GIS, and other areas of geometric computation, but
are studied from a theoretical point of view. Algorithms are
formally analyzed and proven correct.
Otfried Cheong is one of the authors of
the standard textbook on
- Discrete Geometry
geometry is an area of mathematics that studies
combinatorial properties of geometric objects. Going back to
Kepler and Gauss, the field owes much to the work of Paul
We have quite a few visitors from all over the world. See
the visitor log for details.
- Taegyoung Lee, M.Sc. 2019
- Yoon-sung Choi, M.Sc. 2018
- Juyoung Yon, joint Ph.D. with HKUST 2015
- Yujeong Cho, M.Sc. 2015
- Yujin Shin, M.Sc. 2015
- Jaesoon Ha (Dept. of Mathematical Sciences), Ph.D. 2014
- Minho Shin, M.Sc. 2013
- Heuna Kim, M.Sc. 2013
- Jungwoo Yang, M.Sc. 2012
- Hyo-Sil Kim, Ph.D. 2011
- Jeonghwan Jang, M.Sc. 2011
- Aram Han, M.Sc. 2010
- Chang-ryeol Lee, M.Sc. 2009
- Jang-hwan Kim, M.Sc. 2008
- Jung Gun Lim, M.Sc. 2007
- Mira Lee, M.Sc. 2007
- Hyo-Sil Kim, M.Sc. 2007
- Chang-Yul Choi, M.Sc. 2007
- Michael Dobbins
- Hyo-Sil Kim
- Andreas Holmsen
- Iris Reinbacher
- Samuel Hornus
Here is a list of publications by members of the Discrete &
Computational Geometry group that do not already appear on the list
- Hee-Kap Ahn, Sang Won Bae, Jong Min Choi, Matias Korman,
Wolfgang Mulzer, Eunjin Oh, Ji-won Park, André van Renssen, and
Algorithms for Growing Prioritized Disks and
Rectangles. ISAAC 2017: 3:1-3:13.
- Chansu Park, Ji-won Park, Sewon Park, Dongseong Seon, and Martin
Computable Operations on
Compact Subsets of Metric Spaces with Applications to Fréchet
Distance and Shape Optimization. CoRR abs/1701.08402 (2017).
- Steven Chaplick, Fabian Lipp, Ji-won Park,
and Alexander Wolff.
Visibilities with One Obstacle.
International Symposium on Graph
Drawing and Network Visualization (GD 2016), pp. 295-308.
- Hee-Kap Ahn, Siu-Wing Cheng, Hyuk Jun Kweon, and Juyoung
Overlap of convex polytopes under rigid motion.
Computational Geometry: Theory and Application.
- Xaxier Goaoc, Hyo-Sil Kim, and Sylvain Lazard.
Bounded-curvature shortest path through a sequence of points.
SIAM Journal on Computing
- Sariel Har-Peled and Mira Lee.
Weighted geometric set cover problems revisited.
Journal of Computational Geometry, 3:65-85 (2012).
- Jungwoo Yang, Hyungseok Kim, Sangwon Park,
Changki Hong, and Insik Shin.
Implementation of Compositional Scheduling Framework on Virtualization.
Proceedings of the 3rd Workshop on Compositional Theory and
Technology for Real-Time Embedded Systems (CRTS '10) in
conjunction with IEEE RTSS '10, San Diego, CA, USA, November
- Jae-Wan Jang, Myeongjae Jeon, Hyo-Sil Kim,
Heeseung Jo, Jinsu Kim, and Seungryoul Maeng.
Energy Reduction in Consolidated Servers Through Memory-Aware
Virtual Machine Scheduling.
IEEE Transactions on Computers 60:552-564 (2011).
- Radoslav Fulek, Andreas Holmsen, János
convex sets by rays. Symposium on Computational Geometry
- Véronique Cortier, Xavier Goaoc, Mira Lee,
Hyeon-Suk Na. A note on maximally repeated sub-patterns of a point
set. Discrete Mathematics 306:1965-1968 (2006).