Finite point sets and Intersection Patterns (FIP)
Associate team between KAIST and INRIA NGE
Partners
The project-team Gamble (INRIA Nancy Grand Est) and the research group of Professor Holmsen (Department of Mathematical Sciences, KAIST)
Duration
From January 2021 to December 2023
Topics
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 Rd, 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.
Members
- 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)
And past members:
- Ji-won Park (postdoctoral researcher until April 2021)
Exchanges
- 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.
Scientific results
- 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.
- 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.
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.)
- 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.)