The Discrete and Computational Geometry Laboratory existed
from 2005 to 2018 and was formed
by Otfried Cheong
and his graduate students and postdocs.
Research
We did 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
computational geometry.
- Discrete Geometry
Discrete
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
Erdös.
Visitors
We had quite a few visitors from all over the world. See
the visitor log for details.
Alumni
- Ji-won Park, Ph.D. 2019
- 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
Former postdocs
- Michael Dobbins
- Hyo-Sil Kim
- Andreas Holmsen
- Iris Reinbacher
- Samuel Hornus
Publications
Here is a list of publications by members of the Discrete &
Computational Geometry group that do not already appear on the list
of Otfried
Cheong's publications.
- Hee-Kap Ahn, Sang Won Bae, Jong Min Choi, Matias Korman,
Wolfgang Mulzer, Eunjin Oh, Ji-won Park, André van Renssen, and
Antoine Vigneron.
Faster
Algorithms for Growing Prioritized Disks and
Rectangles. ISAAC 2017: 3:1-3:13.
- Chansu Park, Ji-won Park, Sewon Park, Dongseong Seon, and Martin
Ziegler.
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.
Obstructing
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
Yon.
Overlap of convex polytopes under rigid motion.
Computational Geometry: Theory and Application.
47:15-24 (2014).
- Xaxier Goaoc, Hyo-Sil Kim, and Sylvain Lazard.
Bounded-curvature shortest path through a sequence of points.
SIAM Journal on Computing
42:662-684 (2013).
- 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
2010.
- 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
Pach. Intersecting
convex sets by rays. Symposium on Computational Geometry
2008:385-391.
- 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).