Computational Geometry Day at CMI

25th January, 2018

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.

Schedule

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

Abstracts

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.
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.
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.
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.
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.

Xavier Goaoc's other two talks

Date: 22/01/2018
Time: 3:30 pm
Place: Seminar Hall
Title: Some recent trends in discrete and computational geometry.
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: Helly-type theorems and topological combinatorics
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.

Registration