Associate team between KAIST and INRIA NGE

The project-team Gamble (INRIA Nancy Grand Est) and the research group of Professor Holmsen (Department of Mathematical Sciences, KAIST)

From January 2021 to December 2023

This collaboration is at the interface of computer science and mathematics, in the area of discrete and computational geometry. Computational geometry tackles algorithmic problems on geometric data, arising from applied disciplines such as robotics (path planning), CAD (surface reconstruction) or data mining (range searching). The correctness of the proposed solutions is established formally and complexity analyses (of algorithms and problems) are central issues. The resolution of a problem in computational geometry often requires understanding subtle properties of discrete geometric structures like point configurations, polyhedra, arrangements of lines / hyperplanes / algebraic surfaces, etc. These structural questions are central in discrete geometry, a classical subject in mathematics that goes back to at least the ancient Greeks. The communities of computational geometry and discrete geometry blended in the 1980’s into a discrete and computational geometry community. This project tackles questions from two classical research directions

*Intersection patterns of geometric set systems.*The theory of combinatorial convexity revealed many striking properties of families of convex sets that found surprising applications going far beyond their geometric origins. An established line of research explores generalizations of these properties beyond convexity, and some far-reaching conjectures were made by Kalai and Meshulam regarding a homological analogue of the Vapnik-Chervonenkis dimension from learning theory.*Combinatorial abstractions of finite point sets.*Geometric algorithms are often designed over the reals, taking advantage of properties of continuity, closure under arithmetic operations, and geometric figures of*R*, but effectively operate on a combinatorial abstraction of the geometric input, as their courses are determined not by the numerical values given in input, but by the output of the predicate functions. A better understanding of these combinatorial abstractions would allow better design and finer analysis of geometric algorithms, as well as better testing of algorithms or geometric conjectures dealing with finite point sets. This is a classical line of research; an example of a long standing open problem is the tightening of the bounds on the number of halving lines in n-point sets, that is the number of ways in which a line can partition it in two equal-size subset.^{d}

- Minho Choo (PhD student, KAIST)
- Mathilde Bouvel (researcher, CNRS)
- Philippe Chassaing (professor, Université de Lorraine)
- Valentin Féray (researcher, CNRS)
- Xavier Goaoc (professor, Université de Lorraine, co-PI)
- Andreas Holmsen (professor, KAIST, co-PI)
- Florent Koechlin (postdoctoral researcher, INRIA and LORIA)

- Ji-won Park (postdoctoral researcher until April 2021)

- 2021: Due to the coronavirus pandemia, all activities in 2021 were remote. The associate team's budget was effectively 0 euros.
- 2022:
- Xavier Goaoc visited Kaist from Oct. 2nd to Oct. 23rd.
- Florent Koechlin visited Kaist from Oct. 2nd to Oct. 31st.

- 2023:
- Minho Choo visited INRIA Nancy from Feb. 6th to 12th.
- Andreas Holmsen visited INRIA Nancy from June 22nd to July 25th.

*A Stepping-Up Lemma for Topological Set Systems*

Jointly with Zuzana Patáková (Charles University, Prague), Xavier Goaoc and Andreas Holmsen established new properties of intersection patterns of families of sets of bounded topological complexity. The results were presented at the Symposium of Computational Geometry 2021 and an expanded version is currently under preparation.

- Link to the conference paper
- Link to the arXiv version

*Some new results on geometric transversals*

Jointly with Otfried Cheong (SCALGO), Xavier Goaoc and Andreas Holmsen, this paper merges several contributions of line transversals into a single journal article, to appear in Discrete & Computational Geometry, 2024.

- Link to the article

It includes in particular the two following results:

*No weak epsilon nets for lines and convex sets in space*

Jointly with established that the epsilon-net theorem from convex geometry does not generalize to flats in higher dimension. (Submitted for publication.)

- Link to the arXiv version

*The Topology of the set of line Transversals*

Jointly with Otfried Cheong (professor at KAIST at the time, now independent), Xavier Goaoc and Andreas Holmsen investigated the topology of the sets of lines secant to a family of convex sets in 3 dimensions. This allows to simplify the analysis of the intersection patterns of such sets of lines. (Submitted for publication.)

- Link to the arXiv version