Publications

Here you can retrieve copies of most of my papers in PDF/Postscript format.

Journal articles

  1. Sergio Cabello, Siu-Wing Cheng, Otfried Cheong, and Christian Knauer
    Geometric matching and bottleneck problems.
    arxiv:2310.02637
  2. Helmut Alt, Sergio Cabello, Otfried Cheong, Ji-won Park, and Nadja Scharf.
    Packing d-dimensional balls into a d+1-dimensional container.
    arxiv:2110.12711
  3. Otfried Cheong, Xavier Goaoc, and Andreas Holmsen.
    Some new results on geometric transversals.
    Discrete & Computational Geometry 72 (2024) 674–703.
  4. Otfried Cheong, Olivier Devillers, Marc Glisse, and Ji-Won Park.
    Covering families of triangles.
    Periodica Mathematica Hungarica 87 (2023) 86–109.
    hal-03031995
  5. Luis Barba, Otfried Cheong, Michael Gene Dobbins, Rudolf Fleischer, Akitoshi Kawamura, Matias Korman, Yoshio Okamoto, János Pach, Yuan Tang, Takeshi Tokuyama, and Sander Verdonschot.
    Weight Balancing on Boundaries.
    Journal of Computational Geometry 13 (2022) 1–12.
  6. Sergio Cabello, Otfried Cheong, and Michael Gene Dobbins.
    The Inverse Kakeya Problem.
    Periodica Mathematica Hungarica 84 (2022) 70–75.
    arxiv:1912.08477
  7. Siu-Wing Cheng, Otfried Cheong, Taegyoung Lee, and Zhengtong Ren.
    Fitting a graph to one-dimensional data.
    Theoretical Computer Science 867 (2021) 40–49.
    arxiv:1809.02948
  8. Sang Won Bae, Sergio Cabello, Otfried Cheong, Yoonsung Choi, Fabian Stehn, and Sang Duk Yoon.
    The Reverse Kakeya Problem.
    Advances in Geometry 21 (2021) 75–84.
    Proceedings version.
  9. Binay Bhattacharya, Arijit Bishnu, Otfried Cheong, Sandip Das, Arindam Karmakar, and Jack Snoeyink.
    Computation of Spatial Skyline Points.
    Computational Geometry: Theory and Applications 93 (2021) 101698
    arxiv:0909.0814
  10. Ji-won Park and Otfried Cheong.
    Smallest Universal Covers for Families of Triangles.
    Computational Geometry: Theory and Applications 92 (2021) 101686.
  11. Mark de Berg, Sergio Cabello, Otfried Cheong, David Eppstein, and Christian Knauer.
    Covering many points with a small-area box.
    Journal of Computational Geometry 10 (2019) 207–222.
  12. Sang Won Bae, Mark de Berg, Otfried Cheong, Joachim Gudmundsson, and Christos Levcopoulos.
    Shortcuts for the Circle.
    Computational Geometry: Theory and Applications 79 (2019) 37–54.
    arxiv:1612.02412
  13. Hee-Kap Ahn, Judit Abardia, Sang Won Bae, Otfried Cheong, Susanna Dann, Dongwoo Park, and Chan-Su Shin.
    The Minimum Convex Container of Two Convex Polytopes under Translations.
    Computational Geometry: Theory and Applications 77 (2019) 40–50.
  14. Helmut Alt, Kevin Buchin, Steven Chaplick, Otfried Cheong, Philipp Kindermann, Christian Knauer, and Fabian Stehn.
    Placing your Coins on a Shelf.
    Journal of Computational Geometry 9 (2018) 312–327.
  15. Juyoung Yon, Siu-Wing Cheng, Otfried Cheong, and Antoine Vigneron.
    Finding Largest Common Point Sets.
    International Journal of Computational Geometry & Applications 27 (2017) 177–185.
  16. Boris Aronov, Otfried Cheong, Michael Gene Dobbins, and Xavier Goaoc.
    The Number of Holes in the Union of Translates of a Convex Set in Three Dimensions.
    Discrete & Computational Geometry 57 (2017) 104–124.
    arxiv:1502.01779
  17. Jae-Soon Ha, Otfried Cheong, Xavier Goaoc, and Jungwoo Yang.
    Geometric Permutations of Non-Overlapping Unit Balls Revisited.
    Computational Geometry: Theory and Applications 53 (2016) 36–50.
    arxiv:1407.0795
  18. Sergio Cabello, Otfried Cheong, Christian Knauer, and Lena Schlipf.
    Finding Largest Rectangles in Convex Polygons.
    Computational Geometry: Theory and Applications 51 (2016) 67–74.
    arxiv:1405.1223
  19. Otfried Cheong, Sariel Har-Peled, Heuna Kim, and Hyo-Sil Kim.
    On the Number of Edges of Fan-Crossing Free Graphs.
    Algorithmica 73 (2015) 673–695. (On invitation, special issue on ISAAC 2013.)
    arxiv:1311.1976
  20. Otfried Cheong, Radwa El Shawi, and Joachim Gudmundsson.
    A fast algorithm for data collection along a fixed track.
    Theoretical Computer Science 554 (2014) 254–262. (On invitation, special issue on COCOON 2013.)
  21. Hee-Kap Ahn, Sang Won Bae, Otfried Cheong, Joachim Gudmundsson, Takeshi Tokuyama, and Antoine Vigneron.
    A Generalization of the Convex Kakeya Problem.
    Algorithmica 70 (2014) 152–170.
    arxiv:1209.2171
  22. Otfried Cheong and Changryeol Lee.
    Single-Source Dilation-Bounded Minimum Spanning Trees.
    International Journal of Computational Geometry & Applications 23 (2013) 159–170.
    arxiv:1206.6943
  23. Hyo-Sil Kim and Otfried Cheong.
    The Cost of Bounded Curvature.
    Computational Geometry: Theory and Applications 46 (2013) 648–672.
    arxiv:1106.6214
  24. Otfried Cheong, Xavier Goaoc, and Cyril Nicaud.
    Set systems and families of permutations with small traces.
    European Journal of Combinatorics 34 (2013) 229–239.
    arxiv:0912.2979
  25. Otfried Cheong, Xavier Goaoc, Andreas Holmsen.
    Lower bounds to Helly numbers of line transversals to disjoint congruent balls.
    Israel Journal of Mathematics 190 (2012) 213–228.
    arxiv:0906.2924
  26. Hee-Kap Ahn and Otfried Cheong.
    Aligning two convex figures to minimize area or perimeter.
    Algorithmica 62 (2012) 464–479.
    Manuscript available.
  27. Hee-kap Ahn, Otfried Cheong, Jiří Matoušek, Antoine Vigneron.
    Reachability by paths of bounded curvature in a convex polygon.
    Computational Geometry: Theory and Applications 45 (2012) 21–32.
    arxiv:1008.4244
  28. Otfried Cheong, Antoine Vigneron, and Juyoung Yon.
    Reverse nearest neighbor queries in fixed dimension.
    International Journal of Computational Geometry & Applications 21 (2011) 179–188.
    arxiv:0905.4441
  29. Boris Aronov, Otfried Cheong, Xavier Goaoc, and Günter Rote.
    Lines pinning lines.
    Discrete & Computational Geometry 45 (2011) 230–260.
    arxiv:1002.3294
  30. Otfried Cheong, Hazel Everett, Marc Glisse, Joachim Gudmundsson, Samuel Hornus, Sylvain Lazard, Mira Lee, and Hyeon-Suk Na.
    Farthest-Polygon Voronoi Diagrams
    Computational Geometry: Theory and Applications 44 (2011) 234–247.
    arxiv:1001.3593
  31. Prosenjit Bose, Otfried Cheong, and Vida Dujmović.
    A note on the perimeter of fat objects.
    Computational Geometry: Theory and Applications 44 (2011) 1–8.
  32. Mark de Berg, Otfried Cheong, Herman Haverkort, Jung Gun Lim, and Laura Toma.
    The complexity of flow on fat terrains and its I/O-efficient computation.
    Computational Geometry: Theory and Applications 43 (2010) 331–356 (On invitation, special issue on WADS 2007).
    Final version in KOASAS.
  33. Hee-Kap Ahn, Helmut Alt, Tetsuo Asano, Sang Won Bae, Peter Brass, Otfried Cheong, Christian Knauer, Hyeon-Suk Na, Chan-Su Shin, and Alexander Wolff.
    Constructing optimal highways.
    International Journal of Foundations of Computer Science 20 (2009) 3–23.
    Final version in KOASAS.
  34. Hee-Kap Ahn, Sang Won Bae, Otfried Cheong, and Joachim Gudmundsson.
    Aperture-Angle and Hausdorff-Approximation of Convex Figures.
    Discrete & Computational Geometry 40 (2008) 414–429.
    Final version in KOASAS.
  35. Otfried Cheong, Herman Haverkort, and Mira Lee.
    Computing a minimum-dilation spanning tree is NP-hard.
    Computational Geometry: Theory and Applications 41 (2008) 188–205.
    Final version in KOASAS.
  36. Otfried Cheong, Xavier Goaoc, Andreas Holmsen, and Sylvain Petitjean.
    Helly-Type Theorems for Line Transversals to Disjoint Unit Balls.
    Discrete & Computational Geometry 39 (2008) 194–212. (On invitation, special issue on occasion of the twentieth anniversary of the journal.)
    Final version in KOASAS.
  37. Boris Aronov, Mark de Berg, Otfried Cheong, Joachim Gudmundsson, Herman Haverkort, Michiel Smid, and Antoine Vigneron.
    Sparse geometric graphs with small dilation.
    Computational Geometry: Theory and Applications 40 (2008) 207–219.
    Final version in KOASAS.
  38. Otfried Cheong, Hazel Everett, Hyo-Sil Kim, Sylvain Lazard, and René Schott.
    Parabola Separation Queries and their Application to Stone Throwing.
    International Journal of Computational Geometry & Applications 17 (2007) 349–360.
    Final version in KOASAS.
  39. Otfried Cheong and Mira Lee.
    The Hadwiger number of Jordan regions is unbounded.
    Discrete & Computational Geometry 37 (2007) 497–501.
    Final version in KOASAS.
  40. Otfried Cheong, Alon Efrat, and Sariel Har-Peled.
    On Finding a Guard that sees most and a Shop that sells most.
    Discrete & Computational Geometry 37 (2007) 545–563.
    Manuscript available.
  41. Hee-Kap Ahn, Otfried Cheong, Chong-Dae Park, Chan-Su Shin, and Antoine Vigneron.
    Maximizing the overlap of two planar convex sets under rigid motions
    Computational Geometry: Theory and Applications 37 (2007) 3–15. (On invitation, special issue on SoCG 2005).
    Manuscript available.
  42. Hee-Kap Ahn, Siu-Wing Cheng, and Otfried Cheong.
    Casting with Skewed Ejection Direction.
    Algorithmica 44 (2006) 325–342.
    Manuscript available.
  43. Hee-Kap Ahn, Peter Brass, Otfried Cheong, Hyeon-Suk Na, Chan-Su Shin, and Antoine Vigneron.
    Inscribing an axially symmetric polygon and other approximation algorithms for planar convex sets.
    Computational Geometry: Theory and Applications 33 (2006) 152–164.
    Manuscript available.
  44. Prosenjit Bose, Sergio Cabello, Otfried Cheong, Joachim Gudmundsson, Marc van Kreveld, and Bettina Speckmann.
    Area-preserving approximations of polygonal paths.
    Journal of Discrete Algorithms 4 (2006) 554–566.
    Available as Technical Report IMFM-(2004)-PS-942.
  45. Helmut Alt, Otfried Cheong, and Antoine Vigneron.
    The Voronoi diagram of curved objects.
    Discrete & Computational Geometry 34 (2005) 439–453.
    Manuscript available.
  46. Otfried Cheong, Xavier Goaoc, and Hyeon-Suk Na.
    Geometric Permutations of Disjoint Unit Spheres.
    Computational Geometry: Theory and Applications 30 (2005) 253–270.
    Manuscript available.
  47. Tetsuo Asano, Mark de Berg, Otfried Cheong, Hazel Everett, Herman Haverkort, Naoki Katoh, and Alexander Wolff.
    Optimal Spanners for Axis-Aligned Rectangles.
    Computational Geometry: Theory and Applications 30 (2005) 59–77.
    Manuscript available.
  48. Hee-Kap Ahn, Siu-Wing Cheng, Otfried Cheong, and Jack Snoeyink.
    The Reflex-Free Hull.
    International Journal of Computational Geometry & Applications 14 (2004) 453–474.
  49. Siu-Wing Cheng, Otfried Cheong, Hazel Everett, and René van Oostrum.
    Hierarchical Decompositions and Circular Ray Shooting in Simple Polygons.
    Discrete & Computational Geometry 32 (2004) 401–415.
    Available as Technical Report UU-CS-2002-016.
  50. Otfried Cheong, Sariel Har-Peled, Nathan Linial, and Jiří Matoušek.
    The One-Round Voronoi Game.
    Discrete & Computational Geometry 31 (2004) 125–138 (On invitation, special issue on SoCG 2002).
    Available as Technical Report UU-CS-2002-034.
  51. Mark de Berg, Prosenjit Bose, Otfried Cheong, and Pat Morin.
    On Simplifying Dot Maps.
    Computational Geometry: Theory and Applications 27 (2004) 43–62 (On invitation, special issue for the European Workshop on Computational Geometry CG'02).
    Available as Technical Report UU-CS-2002-038.
  52. Hee-Kap Ahn, Siu-Wing Cheng, Otfried Cheong, Mordecai Golin, and René van Oostrum.
    Competitive Facility Location: The Voronoi Game.
    Theoretical Computer Science 310 (2004) 457–467.
    Available as Technical Report UU-CS-2001-45.
  53. Tetsuo Asano, Mark de Berg, Otfried Cheong, Leo J. Guibas, Jack Snoeyink, and Hisao Tamaki.
    Spanning Trees Crossing Few Barriers.
    Discrete & Computational Geometry 30 (2003) 591–606.
    Available as Technical Report UU-CS-2002-012.
  54. Hee-kap Ahn, Otfried Cheong, and René van Oostrum.
    Casting a Polyhedron with Directional Uncertainty.
    Computational Geometry: Theory and Applications 26 (2003) 129–141.
    Available as Technical Report UU-CS-2001-48.
  55. Otfried Cheong, Chan-Su Shin, and Antoine Vigneron.
    Computing Farthest Neighbors on a Convex Polytope.
    Theoretical Computer Science 296 (2003) 47–58 (On invitation, special issue for COCOON'01).
    Available as Technical Report UU-CS-2002-013.
  56. Hee-Kap Ahn, Otfried Cheong, and Chan-Su Shin.
    Building Bridges Between Convex Regions.
    Computational Geometry: Theory and Applications 25 (2003) 161–170 (On invitation, special issue for the European Workshop on Computational Geometry CG'01).
    Available as Technical Report UU-CS-2001-46.
  57. Hyeon-Suk Na, Chung-Nim Lee, and Otfried Cheong.
    Voronoi Diagrams on the Sphere.
    Computational Geometry: Theory and Applications 23 (2002) 183–194.
    Available as Technical Report UU-CS-2001-47.
  58. Hee-Kap Ahn, Mark de Berg, Prosenjit Bose, Siu-Wing Cheng, Dan Halperin, Jiří Matoušek, and Otfried Schwarzkopf.
    Separating an Object from its Cast.
    Computer-Aided Design 34 (2002) 547–559.
    Available as Technical Report UU-CS-1998-16.
  59. Otfried Cheong and René van Oostrum.
    Reaching a Polygon with Directional Uncertainty.
    International Journal of Computational Geometry & Applications 11 (2001) 197–214.
    Available as Technical Report UU-CS-1998-11.
  60. Pankaj Agarwal, Mark de Berg, Jiří Matoušek, and Otfried Schwarzkopf.
    Constructing Levels in Arrangements and Higher Order Voronoi Diagrams.
    SIAM Journal on Computing 27 (1998) 654–667
    Available as Technical Report UU-CS-1995-06.
  61. Mark de Berg, Otfried Cheong, Olivier Devillers, Marc van Kreveld, and Monique Teillaud.
    Computing the Maximum Overlap of Two Convex Polygons Under Translations.
    Theory of Computing Systems 31 (1998) 613–628.
    Available as Technical Report UU-CS-1996-33.
  62. Otfried Schwarzkopf, Ulrich Fuchs, Günter Rote, and Emo Welzl.
    Approximation of Convex Figures by Pairs of Rectangles.
    Computational Geometry: Theory and Applications 10 (1998) 77-87.
    Available as Technical Report .
  63. Pankaj Agarwal, Jiří Matoušek, and Otfried Schwarzkopf.
    Computing Many Faces in Arrangements of Lines and Segments.
    SIAM Journal on Computing 27 (1998) 491–505.
    Available as Technical Report UU-CS-1994-39.
  64. Otfried Schwarzkopf and Micha Sharir.
    Vertical Decomposition of a Single Cell in a Three-Dimensional Arrangement of Surfaces and its Applications.
    Discrete & Computational Geometry 18 (1997) 269–288.
  65. Alon Efrat, Otfried Schwarzkopf.
    Separating and Shattering Long Line Segments.
    Information Processing Letters 64 (1997) 309–314.
    Available as Technical Report .
  66. Mark de Berg, Olivier Devillers, Katrin Dobrindt, Otfried Schwarzkopf.
    Computing a single cell in the overlay of two simple polygons.
    Information Processing Letters 63 (1997) 215–219.
    Available as Technical Report UU-CS-1997-15.
  67. Otfried Schwarzkopf, Jules Vleugels.
    Range Searching in Low-Density Environments.
    Information Processing Letters 60 (1996) 121–127.
    Available as Technical Report UU-CS-1996-26.
  68. Jiří Matoušek and Otfried Schwarzkopf.
    A Deterministic Algorithm for the Three-Dimensional Diameter Problem.
    Computational Geometry: Theory and Applications 6 (1996) 253–262.
    Available as Technical Report RUU-CS-92-45.
  69. Mark de Berg, Marc van Kreveld, Otfried Schwarzkopf, and Jack Snoeyink.
    Point Location in Zones of k-Flats in Arrangements.
    Computational Geometry: Theory and Applications 6 (1996) 131–143.
    Available as Technical Report .
  70. Pankaj Agarwal, Otfried Schwarzkopf, Micha Sharir.
    The Overlay of Lower Envelopes and its Applications.
    Discrete & Computational Geometry 15 (1996) 1–13.
    Available as Technical Report UU-CS-1994-40.
  71. Mark de Berg and Katrin Dobrindt and Otfried Schwarzkopf.
    On Lazy Randomized Incremental Construction.
    Discrete & Computational Geometry 14 (1995) 261–286.
    Available as Technical Report UU-CS-1994-12.
  72. Mark de Berg and Otfried Schwarzkopf.
    Cuttings and Applications.
    International Journal of Computational Geometry & Applications 5 (1995) 343–355.
    Final version in KOASAS.
  73. Martin Aigner and Otfried Schwarzkopf.
    Bounds on the Size of Merging Networks.
    Discrete Applied Mathematics 61 (1995) 187–194.
  74. Mark de Berg, Jiří Matoušek, and Otfried Schwarzkopf.
    Piecewise Linear Paths Among Convex Obstacles.
    Discrete & Computational Geometry 14 (1995) 9–30.
    Available as Technical Report RUU-CS-93-20.
  75. Mark de Berg, Leonidas Guibas, Dan Halperin, Mark Overmars, Otfried Schwarzkopf, Micha Sharir, Monique Teillaud.
    Reaching a Goal with Directional Uncertainty.
    Theoretical Computer Science 140 (1995) 301–317.
    Available as Technical Report UU-CS-1994-09.
  76. Mark de Berg, Mark Overmars, and Otfried Schwarzkopf.
    Computing and Verifying Depth Orders.
    SIAM Journal on Computing 23 (1994) 437–446.
    Available as Technical Report RUU-CS-91-41.
  77. Jiří Matoušek and Otfried Schwarzkopf.
    On ray shooting in convex polytopes.
    Discrete & Computational Geometry 10 (1993) 215–232.
    Available as Technical Report .
  78. Franz Aurenhammer and Otfried Schwarzkopf.
    A Simple On-Line Randomized Incremental Algorithm for Computing Higher-Order Voronoi Diagrams.
    International Journal of Computational Geometry & Applications 2 (1992) 363–381.
    Available as Technical Report .
  79. Pankaj Agarwal, Herbert Edelsbrunner, Otfried Schwarzkopf, and Emo Welzl.
    Euclidean Minimum Spanning Trees and Bichromatic Closest Pairs.
    Discrete & Computational Geometry 6 (1991) 407–422.
  80. Otfried Schwarzkopf,
    Parallel Computation of Distance Transforms.
    Algorithmica 6 (1991) 685–697.
    Amazingly, Algorithmica misprinted the title of the paper, and had to publish an erratum to correct their mistake.

Refereed Conference Proceedings

  1. Taehoon Ahn, Chaeyoon Chung, Hee-Kap Ahn, Sang Won Bae, Otfried Cheong, and Sang Duk Yoon.
    Minimum-Width Double-Slabs and Widest Empty Slabs in High Dimensions.
    In LATIN 2024: Theoretical Informatics
  2. Otfried Cheong, Henry Förster, Julia Katheder, Maximilian Pfister, and Lena Schlipf.
    Weakly and strongly fan-planar graphs.
    Proc. of the 31st International Symposium on Graph Drawing and Network Visualization (GD 2023).
    arxiv:2308.08966
  3. Otfried Cheong, Maximilian Pfister, and Lena Schlipf.
    The thickness of fan-planar graphs is at most three.
    Proc. of the 30th International Symposium on Graph Drawing and Network Visualization (GD 2022).
    arxiv:2208.12324
  4. Helmut Alt, Otfried Cheong, Ji-won Park, and Nadja Scharf.
    Packing 2D disks into a 3D container.
    In WALCOM: Algorithms and Computation, LNCS 11355 (2019), pg 369–380.
  5. Sang Won Bae, Sergio Cabello, Otfried Cheong, Yoonsung Choi, Fabian Stehn, and Sang Duk Yoon.
    The Reverse Kakeya Problem.
    In Proc. 34th Int. Symp. on Computational Geometry (SoCG 2018), pp. 6:1–6:13.
  6. Helmut Alt, Kevin Buchin, Steven Chaplick, Otfried Cheong, Philipp Kindermann, Christian Knauer, and Fabian Stehn.
    Placing your Coins on a Shelf.
    In Proc. of the 28th International Symposium on Algorithms and Computation (ISAAC 2017), pp. 4:1–4:12.
  7. Sang Won Bae, Mark de Berg, Otfried Cheong, Joachim Gudmundsson, and Christos Levcopoulos.
    Shortcuts for the Circle.
    In Proc. of the 28th International Symposium on Algorithms and Computation (ISAAC 2017), pp. 9:1–9:113.
  8. Juyoung Yon, Sang Won Bae, Siu-Wing Cheng, Otfried Cheong, and Bryan T. Wilkinson.
    Approximating Convex Shapes with respect to Symmetric Difference under Homotheties.
    In Proc. 32nd Int. Symp. on Computational Geometry (SoCG 2016), pp. 63:1–63:15.
  9. Boris Aronov, Otfried Cheong, Michael Gene Dobbins, and Xavier Goaoc.
    The Number of Holes in the Union of Translates of a Convex Set in Three Dimensions.
    In Proc. 32nd Int. Symp. on Computational Geometry (SoCG 2016), pp. 10:1–10:16. Best-paper award.
  10. Luis Barba, Otfried Cheong, Jean-Lou De Carufel, Michael Dobbins, Rudolf Fleischer, Akitoshi Kawamura, Matias Korman, Yoshio Okamoto, Janos Pach, Yuan Tang, Takeshi Tokuyama, Sander Verdonschot, and Tianhao Wang.
    Weight Balancing on Boundaries and Skeletons.
    In Proc. 30th Ann. Symp. on Computational Geometry (2014), pp. 436–443.
  11. Otfried Cheong, Sariel Har-Peled, Heuna Kim, and Hyo-Sil Kim.
    On the Number of Edges of Fan-Crossing Free Graphs.
    In Proc. of the 24th International Symposium on Algorithms and Computation (ISAAC), LNCS 8283 (2013), pp. 163–173.
  12. Otfried Cheong, Radwa El Shawi, and Joachim Gudmundsson.
    A fast algorithm for data collection along a fixed track.
    In COCOON 2013: Computing and Combinatorics, LNCS 7936 (2013), pg. 77–88.
  13. Hyo-Sil Kim and Otfried Cheong.
    The Cost of Bounded Curvature.
    In COCOON 2012: Computing and Combinatorics, LNCS 7434 (2012), pg. 252–263.
  14. Hee-Kap Ahn, Sang Won Bae, Otfried Cheong, Joachim Gudmundsson, Takeshi Tokuyama, and Antoine Vigneron.
    A Generalization of the Convex Kakeya Problem.
    In LATIN 2012: Theoretical Informatics, LNCS 7256 (2012), pg 1–12.
  15. Binay Bhattacharya, Arijit Bishnu, Otfried Cheong, Sandip Das, Arindam Karmakar, and Jack Snoeyink.
    Computation of non-dominated points using compact Voronoi diagrams.
    In WALCOM: Algorithms and Computation, LNCS 5942 (2010), pg 82–92.
    arxiv:0909.0814
  16. Otfried Cheong, Xavier Goaoc, and Andreas Holmsen.
    Lower bounds for pinning lines by balls.
    In European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2009), Electronic Notes in Discrete Mathematics, Volume 34 (2009), pg. 567–571.
  17. Otfried Cheong, Joachim Gudmundsson, Hyo-Sil Kim, Daria Schymura, and Fabian Stehn.
    Measuring the similarity of geometric graphs.
    In Proc. 8th International Symposium on Experimental Algorithms (SEA) LNCS 5526(2009), pg .101–112.
  18. Otfried Cheong, Hazel Everett, Marc Glisse, Joachim Gudmundsson, Samuel Hornus, Sylvain Lazard, Mira Lee, and Hyeon-Suk Na.
    Farthest-polygon Voronoi diagrams.
    In Proc. 15th Annu. European Sympos. Algorithms (ESA), LNCS 4698 (2007), pg. 407–418.
  19. Mark de Berg, Otfried Cheong, Herman Haverkort, Jung Gun Lim, and Laura Toma.
    I/O-efficient flow modeling on fat terrains.
    In Proc. 10th Workshop on Algorithms and Data Structures (WADS), LNCS 4619 (2007), pg. 239–250.
  20. Hee-Kap Ahn, Sang Won Bae, Otfried Cheong, and Joachim Gudmundsson.
    Aperture-angle and Hausdorff-approximation of convex figures.
    In Proc. 23rd Ann. Symp. on Computational Geometry, (2007), pg. 37–45.
  21. Otfried Cheong, Herman Haverkort, and Mira Lee.
    Computing a minimum-dilation spanning tree is NP-hard.
    In Computing: The Australasian Theory Symposium (CATS), CRPIT Vol. 65, 2007, pg. 15–24.
  22. Hee-Kap Ahn, Helmut Alt, Tetsuo Asano, Sang Won Bae, Peter Brass, Otfried Cheong, Christian Knauer, Hyeon-Suk Na, Chan-Su Shin, and Alexander Wolff.
    Constructing optimal highways.
    In Computing: The Australasian Theory Symposium (CATS), CRPIT Vol. 65, 2007, pg. 7–14.
  23. Otfried Cheong, Hazel Everett, Hyo-Sil Kim, Sylvain Lazard, and René Schott.
    Throwing stones inside simple polygons.
    In Proc. of the 2nd International Conference on Algorithmic Aspects in Information and Management (AAIM), LNCS 4041 (2006), pg. 185–193.
  24. Hee-Kap Ahn and Otfried Cheong.
    Stacking and bundling two convex polygons.
    In Proc. of the 16th International Symposium on Algorithms and Computation (ISAAC), LNCS 3827 (2005), pg. 882–891.
  25. Boris Aronov, Mark de Berg Otfried Cheong, Joachim Gudmundsson, Herman Haverkort, and Antoine Vigneron.
    Sparse geometric graphs with small dilation.
    In Proc. of the 16th International Symposium on Algorithms and Computation (ISAAC), LNCS 3827 (2005), pg. 50–59.
  26. Hee-Kap Ahn, Otfried Cheong, Chong-Dae Park, Chan-Su Shin, and Antoine Vigneron.
    Maximizing the overlap of two planar convex sets under rigid motions
    In Proc. 21st Ann. Symp. on Computational Geometry, (2005), pg. 356-363
  27. Otfried Cheong, Xavier Goaoc, and Andreas Holmsen.
    Hadwiger and Helly-type theorems for disjoint unit spheres in R3.
    In Proc. 21st Ann. Symp. on Computational Geometry, (2005), pg. 10-15.
  28. Hee-Kap Ahn, Peter Brass, Otfried Cheong, Hyeon-Suk Na, Chan-Su Shin, and Antoine Vigneron.
    Approximation algorithms for inscribing or circumscribing an axially symmetric polygon to a convex polygon.
    In Proc. 10th Annual Intern. Computing and Combinatorics Conference (COCOON), LNCS 3106 (2004), pg. 259–268.
  29. Otfried Cheong, Alon Efrat, and Sariel Har-Peled.
    On finding a guard that sees most and a shop that sells most.
    In Proc. 15th ACM-SIAM Sympos. Discrete Algorithms (SODA) (2004), pg. 1091–1100.
  30. Otfried Cheong, Xavier Goaoc, and Hyeon-Suk Na.
    Disjoint Unit Spheres Admit At Most Two Line Transversals.
    In Proc. 11th Annu. European Sympos. Algorithms (ESA), LNCS 2832 (2003), pg. 127–135.
    Available as Technical Report INRIA/RR-4854.
  31. Hee-kap Ahn, Otfried Cheong, and René van Oostrum.
    Casting a polyhedron with directional uncertainty.
    In Proc. of the 13th International Symposium on Algorithms and Computation (ISAAC), LNCS 2518 (2002), pg. 274–285.
    Available as Technical Report UU-CS-2001-48.
  32. Otfried Cheong, Sariel Har-Peled, Nathan Linial, Jiří Matoušek.
    The One-Round Voronoi Game.
    In Proc. 18th Ann. Symp. on Computational Geometry, (2002).
  33. Otfried Cheong, Chan-Su Shin, and Antoine Vigneron.
    Computing Farthest Neighbors on a Convex Polytope.
    In 7th Annual International Computing and Combinatorics Conference (ISAAC), LNCS 2108 (2001), pg. 159–169.
    Available as Technical Report UU-CS-2002-013.
  34. Hee-Kap Ahn, Siu-wing Cheng, Otfried Cheong, Mordecai Golin, and René van Oostrum.
    Competitive Facility Location along a Highway.
    In 7th Annual International Computing and Combinatorics Conference (ISAAC), LNCS 2108 (2001), pg. 237–246.
    Available as Technical Report UU-CS-2001-45.
  35. Jae-Ha Lee, Otfried Cheong, Woo-Cheol Kwon, Sung Yong Shin, and Kyung-Yong Chwa.
    Approximation of Curvature-Constrained Shortest Paths through a Sequence of Points.
    In Algorithms — ESA 2000, LNCS 1879 (2000), pg. 314–325.
    Manuscript available.
  36. Hee-kap Ahn, Otfried Cheong, Jiří Matoušek, and Antoine Vigneron.
    Reachability by paths of bounded curvature in convex polygons.
    In Proc. 16th Ann. Symp. on Computational Geometry, (2000), pg. 251–259.
    Manuscript available.
  37. Siu-Wing Cheng, Otfried Cheong, Hazel Everett, and René van Oostrum
    Hierarchical Vertical Decompositions, Ray Shooting, and Circular Arc Queries in Simple Polygons.
    In Proc. 15th Ann. ACM Symp. Comput. Geom., 1999, pg. 227–236.
  38. Tetsuo Asano, Mark de Berg, Otfried Cheong, Leo J. Guibas, Jack Snoeyink, and Hisao Tamaki
    Spanning Trees Crossing Few Barriers.
    In Proc. 15th Ann. ACM Symp. Comput. Geom., 1999, pg. 41–48.
    Available as Technical Report UU-CS-2002-012.
  39. Hee-Kap Ahn, Siu-Wing Cheng, and Otfried Cheong.
    Casting with Skewed Ejection Direction.
    In 9th Ann. International Symp. on Algorithms and Computation, LNCS 1533 (1998), pg. 139–148.
  40. Hee-Kap Ahn, Mark de Berg, Prosenjit Bose, Siu-Wing Cheng, Dan Halperin, Jiří Matoušek, and Otfried Schwarzkopf.
    Separating an Object from its Cast.
    In Proc. 13th Ann. ACM Symp. Comput. Geom., 1997, pg. 221–230.
    Available as Technical Report UU-CS-1998-16.
  41. Mark de Berg, Olivier Devillers, Marc van Kreveld, Otfried Schwarzkopf, and Monique Teillaud.
    Computing the Maximum Overlap of Two Convex Polygons Under Translations.
    In Proc. 7th Ann. International Symp. on Algorithms and Computation, LNCS 1178 (1996), pg. 126–135.
    Available as Technical Report UU-CS-1996-33.
  42. Alon Efrat and Otfried Schwarzkopf.
    Separating and Shattering Long Line Segments.
    In Proc. 7th Ann. International Symp. on Algorithms and Computation, LNCS 1178 (1996), pg. 36–44.
  43. Otfried Schwarzkopf and Micha Sharir.
    Vertical Decomposition of a Single Cell in a Three-Dimensional Arrangement of Surfaces and its Applications.
    In Proc. 12th Ann. ACM Symp. Comput. Geom., 1996, pg. 20–29.
  44. Mark Overmars, Anil Rao, Otfried Schwarzkopf, and Chantal Wentink.
    Immobilizing Polygons against a Wall.
    In Proc. 11th Ann. ACM Symp. Comput. Geom., (1995), pg. 29–38.
    Available as Technical Report UU-CS-1996-11.
  45. Helmut Alt and Otfried Schwarzkopf.
    The Voronoi Diagram of Curved Objects.
    In Proc. 11th Ann. ACM Symp. Comput. Geom., (1995), pg. 89–97.
    There is a serious error in Lemma 1 (b) of this paper. A corrected version has appeared in Discrete & Computational Geometry , see above.
  46. Pankaj Agarwal, Otfried Schwarzkopf, and Micha Sharir.
    The Overlay of Lower Envelopes in Three Dimensions and Its Applications.
    In Proc. 11th Ann. ACM Symp. Comput. Geom., (1995), pg. 182–189.
    Available as Technical Report UU-CS-1994-40.
  47. Pankaj Agarwal, Mark de Berg, Jiří Matoušek, and Otfried Schwarzkopf.
    Constructing Levels in Arrangements and Higher Order Voronoi Diagrams.
    In Proc. 10th Ann. ACM Symp. Comput. Geom., (1994), pg. 67–75.
    Available as Technical Report UU-CS-1995-06.
  48. Pankaj Agarwal, Jiří Matoušek, Otfried Schwarzkopf.
    Computing Many Faces in Arrangements of Lines and Segments.
    In Proc. 10th Ann. ACM Symp. Comput. Geom., (1994), pg. 76–84.
    Available as Technical Report UU-CS-1994-39.
  49. Mark de Berg and Katrin Dobrindt and Otfried Schwarzkopf.
    On Lazy Randomized Incremental Construction.
    In Proc. 25th Ann. ACM Symp. Theory Comput., (1994), pg. 105–114.
    Available as Technical Report UU-CS-1994-12.
  50. Mark de Berg, Jiří Matoušek, and Otfried Schwarzkopf.
    Piecewise Linear Paths Among Convex Obstacles.
    In Proc. 25th Ann. ACM Symp. Theory Comput. (1993), pg. 505–514.
    Available as Technical Report RUU-CS-93-20.
  51. Jiří Matoušek, Otfried Schwarzkopf.
    A Deterministic Algorithm for the Three-Dimensional Diameter Problem.
    In Proc. 25th Ann. ACM Symp. Theory Comput. (1993), pg. 478–484.
    Available as Technical Report RUU-CS-92-45.
  52. Otfried Schwarzkopf.
    Computing Convolutions on Mesh-Like Structures.
    In Proc. Seventh International Parallel Processing Symp. (1993), pg. 695–699.
    Manuscript available.
  53. Mark de Berg, Leonidas Guibas, Dan Halperin, Mark Overmars, Otfried Schwarzkopf, Micha Sharir, and Monique Teillaud.
    Reaching a Goal with Directional Uncertainty.
    In Proc. 4th Ann. Internat. Symp. Algorithms Comput. LNCS 762 (1993), pg. 1–10.
    Available as Technical Report UU-CS-1994-09.
  54. Otfried Schwarzkopf.
    Ray shooting in convex polytopes.
    In Proc. 8th Ann. Symp. on Computational Geometry (1992), pg. 286–295.
  55. Mark de Berg, Mark Overmars, and Otfried Schwarzkopf.
    Computing and verifying depth orders.
    In Proc. 8th Ann. Symp. on Computational Geometry (1992), pg. 138–145.
    Available as Technical Report RUU-CS-91-41.
  56. Jiří Matoušek, Otfried Schwarzkopf.
    Linear optimization queries.
    In Proc. 8th Ann. Symp. on Computational Geometry (1992), pg. 16–25.
  57. Franz Aurenhammer, Otfried Schwarzkopf.
    A Simple On-line Randomized Incremental Algorithm for Computing Higher Order Voronoi Diagrams.
    In Proc. 7th Ann. Symp. on Computational Geometry, (1991), pg. 142–151.
  58. Otfried Schwarzkopf.
    Dynamic Maintenance of Geometric Structures Made Easy.
    In Proc. 32nd Symp. Foundations of Computer Science, (1991), pg. 197–206.
  59. Otfried Schwarzkopf, Ulrich Fuchs, Günter Rote, Emo Welzl.
    Approximation of convex figures by pairs of rectangles.
    In Proc. 7th Ann. Symp. on Theoretical Aspects of Computer Science, (1990), pg. 240–249.
  60. Pankaj Agarwal, Herbert Edelsbrunner, Otfried Schwarzkopf, Emo Welzl.
    Euclidean Minimum Spanning Trees and Bichromatic Closest Pairs.
    In Proc. 6th Ann. Symp. on Computational Geometry, (1990), pg. 203–210.
  61. Otfried Schwarzkopf.
    Parallel Computation of Discrete Voronoi Diagrams.
    In Proc. 6th Ann. Symp. on Theoretical Aspects of Computer Science, LNCS 349 (1989), pg. 193–204.

Books and book chapters

  1. Otfried Cheong, Ketan Mulmuley, and Edgar Ramos.
    Randomization and derandomization.
    Chapter 44 in the 3rd edition of Handbook of Discrete and Computational Geometry, Csaba Toth, Joseph O'Rourke, and Jacob E. Goodman (Eds.), Chapman and Hall/CRC, 2017
  2. Otfried Cheong, Kyung-Yong Chwa, and Kunsoo Park.
    Algorithms and Computation: Proceedings of the 21st International Symposium (ISAAC 2010). Part II.
    LNCS 6507, Springer-Verlag, 2010.
  3. Otfried Cheong, Kyung-Yong Chwa, and Kunsoo Park.
    Algorithms and Computation: Proceedings of the 21st International Symposium (ISAAC 2010). Part I.
    LNCS 6506, Springer-Verlag, 2010.
  4. Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars.
    Computational Geometry: Algorithms and Applications, Third Edition.
    Springer-Verlag, 2008.
  5. Mark de Berg, Marc van Kreveld, Mark Overmars, Otfried Schwarzkopf.
    Geometria obliczeniowa: algorytmy i zastosowania (Computational Geometry: Algorithms and Applications, Polish). Translated by Miroslaw Kowaluk.
    Wydawnictwa Naukowo-Techniczne, Warsaw 2007.
  6. Nina Amenta and Otfried Cheong (Editors).
    Proceedings of the twenty-second annual symposium on Computational Geometry.
    ACM Press, New York, 2006.
  7. Otfried Cheong, Ketan Mulmuley, and Edgar Ramos.
    Randomization and derandomization.
    Chapter 40 in the 2nd edition of Handbook of Discrete and Computational Geometry, Jacob E. Goodman and Joseph O'Rourke (Eds.), CRC Press, Boca Raton 2004
  8. Mark de Berg, Marc van Kreveld, Mark Overmars, Otfried Schwarzkopf.
    Computational Geometry: Algorithms and Applications, Second Edition.
    Springer-Verlag, 2000.
  9. Mark de Berg, Marc van Kreveld, Mark Overmars, Otfried Schwarzkopf.
    Kompyuuta Jiometori (Computational Geometry: Algorithms and Applications, Japanese). Translated by Tetsuo Asano.
    Kindaikagaku, 2000.
  10. Mark de Berg, Marc van Kreveld, Mark Overmars, Otfried Schwarzkopf.
    Computational Geometry: Algorithms and Applications.
    Springer-Verlag, 1997.
  11. Ketan Mulmuley and Otfried Schwarzkopf.
    Randomized algorithms.
    Chapter 34 in Handbook of Discrete and Computational Geometry, Jacob E. Goodman and Joseph O'Rourke (Eds.), CRC Press, Boca Raton 1997

Invited lectures at conferences with proceedings

  1. Otfried Cheong
    How Can Biclique Covers Help in Matching Problems
    In Proc. 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)
  2. Otfried Cheong
    Line Transversals and Pinning Numbers.
    In Third International Workshop on Algorithms and Computation (WALCOM), LNCS 5431 (2009), pg. 44–46.
  3. Otfried Cheong
    The Harmony of Spheres.
    In Proc. 19th Annual Canad. Conf. Comput. Geom., (2007), pg. 7.

Other publications

  1. Hee-Kap Ahn, Sang Won Bae, Otfried Cheong, Dongwoo Park, and Chan-Su Shin.
    Minimum Convex Container of Two Convex Polytopes under Translations.
    Proc. 26th Canad. Conf. Comput. Geom. (2014).
  2. Otfried Cheong, Sariel Har-Peled, Heuna Kim, and Hyo-Sil Kim.
    On the number of edges of a fan-crossing free graph.
    6th Annual Meeting of the Asian Association for Algorithms and Computation (2013).
  3. Otfried Cheong and Yoshio Okamoto.
    Guest editor's foreword.
    International Journal of Computational Geometry & Applications 22 (2012) 1–2.
  4. Hyo-Sil Kim and Otfried Cheong.
    The Cost of Bounded Curvature.
    Computational Geometry: Young Researchers Forum (2012).
  5. Otfried Cheong and Changryeol Lee.
    Anchored Dilation-Bounded Minimum Spanning Tree.
    5th Annual Meeting of the Asian Association for Algorithms and Computation (2012).
  6. Otfried Cheong, Hyo-Sil Kim, and Lena Schlipf.
    Computing Barrier Resilience for Line Segments is NP-hard and APX-hard.
    14th Japan-Korea Joint Workshop on Algorithms and Computation (2011).
  7. Mira Lee and Otfried Cheong.
    Imprecise Convex Hulls.
    14th Japan-Korea Joint Workshop on Algorithms and Computation (2011).
  8. Otfried Cheong, Antoine Vigneron, and Juyoung Yon.
    Reverse nearest neighbor queries in fixed dimension.
    13th Japan-Korea Joint Workshop on Algorithms and Computation (2010).
  9. Prosenjit Bose, Otfried Cheong, and Vida Dujmović.
    On the perimeter of fat objects.
    Proc. 22nd Canad. Conf. Comput. Geom. (2010).
  10. Nina Amenta and Otfried Cheong.
    Guest editor's foreword.
    Discrete & Computational Geometry 41 (2009) 363–364.
  11. Nina Amenta and Otfried Cheong.
    Guest editor's foreword.
    International Journal of Computational Geometry & Applications 18 (2008) 507–508.
  12. Hee-Kap Ahn, Sang-Won Bae, and Otfried Cheong.
    A geometric proof on shortest paths of bounded curvature (in Korean).
    Journal of KISS: Computer Systems and Theory, 34 (2007) 132–137.
  13. Otfried Cheong, Xavier Goaoc, Andreas Holmsen, and Sylvain Petitjean.
    Helly-Type Theorems for Line Transversals to Disjoint Unit Balls.
    Proc. 22nd European Workshop on Computational Geometry, 2006.
  14. Hee-Kap Ahn, Mark de Berg, Otfried Cheong, Herman Haverkort, Frank van der Stappen, and Laura Toma.
    River networks and watershed maps of triangulated terrains revisited.
    Proc. 22nd European Workshop on Computational Geometry, 2006.
  15. Boris Aronov, Mark de Berg Otfried Cheong, Joachim Gudmundsson, Herman Haverkort, and Antoine Vigneron.
    Sparse geometric graphs with small dilation.
    Proc. Korea-Japan Joint Workshop on Algorithms and Computation (WAAC) 2005.
  16. Tetsuo Asano, Mark de Berg, Otfried Cheong, Hazel Everett, Herman Haverkort, Naoki Katoh, and Alexander Wolff.
    Optimal spanners for axis-aligned rectangles.
    Proc. 20th European Workshop on Computational Geometry, pg. 97–100, 2004.
  17. Mark de Berg, Prosenjit Bose, Otfried Cheong, and Pat Morin.
    On Simplifying Dot Maps.
    Proc. 18th European Workshop on Computational Geometry, pg. 96–100, 2002.
  18. Hee-kap Ahn, Siu-Wing Cheng, Otfried Cheong, and Jack Snoeyink.
    The reflex-free hull.
    In Proc. 13th Canad. Conf. Comput. Geom., (2001).
  19. Otfried Cheong and René van Oostrum.
    The Visibility Region of Points in a Simple Polygon.
    In Proc. 11th Canad. Conf. Comput. Geom., (1999), pg. 87–90.
    Manuscript available.
  20. Hee-kap Ahn, Siu-Wing Cheng, and Otfried Cheong.
    Casting with Skewed Ejection Direction Revisited.
    In Proc. 11th Canad. Conf. Comput. Geom., (1999), pg. 128–131.
    Manuscript available.
  21. Otfried Schwarzkopf.
    The Hyperlatex Story.
    TUGboat, 16(1995) 159–162.
    Postscript version
  22. Chantal Wentink and Otfried Schwarzkopf.
    Motion Planning for Vacuum Cleaner Robots.
    In Proc. 6th Canad. Conf. Comput. Geom., (1994), pg. 51–56.
  23. Otfried Schwarzkopf.
    The extensible drawing editor Ipe.
    In Proc. 11th Ann. ACM Symp. Comput. Geom., (1995), pg. C10–C11.
    Postscript version
Otfried Cheong