Computational Geometry arose as a new field in the past few decades, through fruitful interactions between classical subjects like geometry, combinatorics and computer science. It is now a very active area of research, devoted to understanding the structure and complexity of discrete geometric structures as well as the design and analysis of geometric algorithms for their manipulation. Key examples of the objects studied are arrangements (of lines, curves, hyperplanes), polytopes, tilings, packings and coverings, oriented matroids, simplicial complexes, geometric graphs, transversals to families of convex sets, Voronoi diagrams, etc. This field has strong relations to well-established mathematical areas such as algebra (e.g., toric varieties, symmetry groups, real algebraic geometry), topology (e.g., combinatorial manifolds, triangulations), probability theory (e.g., randomization techniques, geometric probability), and combinatorics (e.g., extremal graph and hypergraph theory). These relations enable this field to serve as the language and mathematical foundation for solving problems in many other areas.

The purpose of this one-day meeting is two-fold. First, it
will bring together Chennai-based mathematicians and computer
scientists interested in areas like algorithms, combinatorics,
graph theory, discrete geometry, (algebraic) topology etc., to
give lectures on new results, exchange ideas, problems and
conjectures. Second, Xavier Goaoc
from Université Paris-Est Marne-la-Vallée is visiting CMI during
that week; he is a also a member of the `algorithmic geometry'
group at the LIGM laboratory.
He is interested in exploring a possibility of Indo-French
collaboration in the field of Computational Geometry. This
meeting will provide a platform for an interaction with Xavier
Goaoc.

If you are interested in attending this meeting then do register
here. For anything else feel free to drop me
an email - pdeshpande AT cmi.ac.in

As of part of his visit, Xavier Goaoc is going to deliver two more talks at CMI. The details of these talks are here .

All the talks (except the last talk) will be held in the NKN Hall (new building). Lunch will be provided to all the participants.

Time | Talks |
---|---|

9:30 - 10:20 | Sourav Chakraborty (CMI) Helly-Type Theorems in Property Testing |

10:20 - 10:50 | Coffee break |

10:50 - 11:40 | N. S. Narayanaswamy (IIT-M) A Survey of The Conflict-Free Colouring Problem |

11:40 - 11:50 | Break |

11:50 - 12:40 | Samir Datta (CMI) Bounded genus graph problems and bounded space computation |

12:40 pm - 1:55 pm | Lunch |

2 pm - 3 pm | Saket Saurabh (IMSc) Art Galleray: Combinatorial and Algorithmic Results |

3:05 pm - 3:25 pm | Coffee break |

3:30 pm - 4:40 pm | Xavier Goaoc (Université Paris-Est Marne-la-Vallée) Shatter functions of geometric hypergraphs |

Sourav Chakraborty, **Helly-Type Theorems in Property Testing**

Helly’s theorem is a fundamental result in discrete geometry, describing the ways in which convex sets intersect with each other. If \(S\) is a set of n points in \(\mathbb{R}^d\), we say that \(S\) is \((k, G)\)-clusterable if it can be partitioned into \(k\) clusters (subsets) such that each cluster can be contained in a translated copy of a geometric object \(G\). In this talk, as an application of Helly’s theorem, by taking a constant size sample from \(S\), we present a testing algorithm for \((k, G)\)--clustering, i.e., to distinguish between two cases: when \(S\) is \((k, G)\)--clusterable, and when it is \(\epsilon\)-far from being \((k, G)\)--clusterable. A set \(S\) is \(\epsilon\)-far from being \((k, G)\)--clusterable if at least \(\epsilon n\) points need to be removed from \(S\) to make it \((k, G)\)--clusterable. We solve this problem for \(k = 1\) and when \(G\) is a symmetric convex object. For \(k > 1\), we solve a weaker version of this problem.

Helly’s theorem is a fundamental result in discrete geometry, describing the ways in which convex sets intersect with each other. If \(S\) is a set of n points in \(\mathbb{R}^d\), we say that \(S\) is \((k, G)\)-clusterable if it can be partitioned into \(k\) clusters (subsets) such that each cluster can be contained in a translated copy of a geometric object \(G\). In this talk, as an application of Helly’s theorem, by taking a constant size sample from \(S\), we present a testing algorithm for \((k, G)\)--clustering, i.e., to distinguish between two cases: when \(S\) is \((k, G)\)--clusterable, and when it is \(\epsilon\)-far from being \((k, G)\)--clusterable. A set \(S\) is \(\epsilon\)-far from being \((k, G)\)--clusterable if at least \(\epsilon n\) points need to be removed from \(S\) to make it \((k, G)\)--clusterable. We solve this problem for \(k = 1\) and when \(G\) is a symmetric convex object. For \(k > 1\), we solve a weaker version of this problem.

N. S. Narayanaswamy, **A Survey of The Conflict-Free Colouring Problem **

In this survey talk we present some results on the conflict free colouring problem. The conflict-free colouring problem is to assign colours to the vertices of a hypergraph such that each hyperedge has a colour that has not been given to any other vertex in the hyperedge. The problem has received extensive attention over the last decade starting with a paper by Smorodinsky and Even, and is of significant interest.

In this survey talk we present some results on the conflict free colouring problem. The conflict-free colouring problem is to assign colours to the vertices of a hypergraph such that each hyperedge has a colour that has not been given to any other vertex in the hyperedge. The problem has received extensive attention over the last decade starting with a paper by Smorodinsky and Even, and is of significant interest.

Samir Datta, * ***Bounded genus graph problems and bounded space computation **

For many graph theory problems, restricting the input to planar and bounded genus graphs enables efficient parallel algorithms. We survey some classes of these restricted problems where the notion of parallelism is characterised by bounding the space of computation.

For many graph theory problems, restricting the input to planar and bounded genus graphs enables efficient parallel algorithms. We survey some classes of these restricted problems where the notion of parallelism is characterised by bounding the space of computation.

Saket Saurabh, ** Art Gallery: Combinatorial and Algorithmic Results**

Art gallery problems are on of the most well studied problems algorithmically and combinatorially in Computational Geometry. In this talk we survey some of the known and unknown results in this area.

Art gallery problems are on of the most well studied problems algorithmically and combinatorially in Computational Geometry. In this talk we survey some of the known and unknown results in this area.

Xavier Goaoc, **Shatter
functions of geometric hypergraphs.**

*Abstract*: In combinatorial and computational geometry,
the complexity of system of sets is often studied via its
shatter function. I will introduce these functions, and discuss
how their asymptotic growth rate is governed from a single of
its values, in the spirit of the classical "Vapnik-Chernonenkis
dimension" of hypergraphs. In particular, I will describe a
probabilistic construction that refutes a conjecture of Bondy
and Hajnal. The talk will start from first principles.

Time: 3:30 pm

Place: Seminar Hall

Title:

Abstract: I will give a general introduction to the field of discrete and computational geometry, starting with some classical structures (arrangements, Delaunay triangulations and Voronoi diagrams) and continuing with some recent developments relying on algebraic and topological methods. The talk will not assume any prior knowledge.

Date: 24/01/2018

Time: 3:30 pm

Place: Seminar Hall

Title:

Abstract: To study or manipulate a geometric object, it is sometimes useful to consider an associated combinatorial structure, which emphasizes some of its properties. I will illustrate this idea on the analysis of the intersection patterns of subsets of the space. By a theorem of Helly, if four convex sets in the plane intersect triple-wise, then they must have a point in common. This property gives rise to many generalizations, relaxing for example the assumption of convexity. I will discuss how some techniques from topological combinatorics (embeddings of graphs or simplicial complexes, homology of nerve complexes and nerve theorem) allow to unify many of these generalizations.