University of Bonn · Institute of Computer Science · Algorithms and Complexity

Sidebar

Current Semester (WiSe 2025/26)

Bachelor
Master

Optimization Techniques for Geometric Set Systems

This seminar is offered for students enrolled in the Mathematics Master as module S4C1 “Graduate Seminar on Discrete Optimization” as well as students enrolled in the Computer Science Master as module MA-INF 1205 with the same title. The seminar is organized and held by Prof. Dr. Anne Driemel.

The goal of the seminar is for each participant to:

  • Study a scientific paper (see references below)
  • Present the main ideas of the paper in a talk (45 minutes excl. questions)
  • Participate in discussions on the topic of the seminar
  • Submit a written report (in own words) (~10 pages)

Schedule

If you want to participate in the seminar, please contact Prof. Dr. Anne Driemel with your topic preference from the literature list. The first preparation meeting will take place on 13 April 2026 at 16:00 in room 2.074 (Informatik V, 2. OG) . The meeting room is located in the computer science building at Friedrich Hirzebruch Allee 8.

Content

Geometric intersection graphs appear in many applications. They represent the intersections among a set of geometric objects, such as disks, pseudodisks, or rectangles, by representing each object by a node and each pair of intersecting objects by an edge. A maximum independent set in this graph corresponds to a maximum set of pairwise non-overlapping regions. This problem has diverse applications, for example for label placement in maps, VLSI-design and data mining. A closely related problem is the minimum hitting set problem. A hitting set (or piercing set) corresponds to a set of points such that all objects contain a point from this set. These problems are NP-hard in general graphs, but allow for efficient approximation algorithms (PTAS) in the geometric setting. In this seminar, we will study the development of several interconnected techniques in this area.

Literature (tentative)

  1. Agarwal, P.K., Ezra, E. and Sharir, M. (2012) “Near-Linear Approximation Algorithms for Geometric Hitting Sets,” Algorithmica, 63(1–2), pp. 1–25. Available at: https://doi.org/10.1007/s00453-011-9517-2.
  2. Agarwal, P.K. and Mustafa, N.H. (2006) “Independent set of intersection graphs of convex objects in 2D,” Computational Geometry, 34(2), pp. 83–95. Available at: https://doi.org/10.1016/j.comgeo.2005.12.001.
  3. Bringmann, K. et al. (2015) “Hitting Set for hypergraphs of low VC-dimension.” Available at: https://doi.org/10.48550/ARXIV.1512.00481.
  4. Brönnimann, H. and Goodrich, M.T. (1995) “Almost optimal set covers in finite VC-dimension,” Discrete & Computational Geometry, 14(4), pp. 463–479. Available at: https://doi.org/10.1007/BF02570718.
  5. Bus, N., Mustafa, N.H. and Ray, S. (2018) “Practical and efficient algorithms for the geometric hitting set problem,” Discrete Applied Mathematics, 240, pp. 25–32. Available at: https://doi.org/10.1016/j.dam.2017.12.018.
  6. Chan, T.M. (2003) “Polynomial-time approximation schemes for packing and piercing fat objects,” Journal of Algorithms, 46(2), pp. 178–189. Available at: https://doi.org/10.1016/S0196-6774(02)00294-8.
  7. Erlebach, T., Jansen, K. and Seidel, E. (2005) “Polynomial-Time Approximation Schemes for Geometric Intersection Graphs,” SIAM Journal on Computing, 34(6), pp. 1302–1323. Available at: https://doi.org/10.1137/S0097539702402676.
  8. Even, G., Rawitz, D. and Shahar, S. (Moni) (2005) “Hitting sets when the VC-dimension is small,” Information Processing Letters, 95(2), pp. 358–362. Available at: https://doi.org/10.1016/j.ipl.2005.03.010.
  9. Jartoux, B. and Mustafa, N.H. (2022) “A Tight Analysis of Geometric Local Search,” Discrete & Computational Geometry, 67(2), pp. 361–379. Available at: https://doi.org/10.1007/s00454-021-00343-y.
  10. Lauen, S. (2013) “Geometric Set Cover and Hitting Sets for Polytopes in R3,” LIPIcs, Volume 1, STACS 2008. Edited by S. Albers and P. Weil, 1, pp. 479–490. Available at: https://doi.org/10.4230/LIPICS.STACS.2008.1367.
  11. Liu, G. and Wang, H. (2025a) “An Optimal Algorithm for Half-plane Hitting Set.” Available at: https://doi.org/10.48550/ARXIV.2501.02195.
  12. Liu, G. and Wang, H. (2025b) “Minimum-Weight Half-Plane Hitting Set.” Available at: https://doi.org/10.48550/ARXIV.2506.16979.
  13. Mustafa, N.H. and Ray, S. (2010) “Improved Results on Geometric Hitting Set Problems,” Discrete & Computational Geometry, 44(4), pp. 883–895. Available at: https://doi.org/10.1007/s00454-010-9285-9.

Page Tools

Imprint/Impressum