Personal Informations

Thomas IWASZKO
Ph.D. student in Computer Science
contact: iwaszko[at]unistra[dot]fr

Ongoing thesis work (general readers-accessible abstract)

In computer science, using data structures to improve algorithms time complexity is a common practice. The Voronoi Decomposition (VD) of a metric space is a particular data structure which has been extensively studied, e.g. Aurenhammer's survey (1991). The VD can speed up many simple geometric algorithms. However, algorithms which use data more complex than points and distance measures are out of range for this kind of enhancement.

We focused on the « empty circle property » of the VD to overtake this restriction. To test our hypothesis that a data structure extending this property to more complex geometric shapes exist, we looked for a rigorous shape model, stated a more general « empty shape property » and searched how to define plane regions satisfying it.

We found a simple shape model, namely a finite set of overlapping circles. Thanks to this model, we defined two global geometric operations on shapes, along with special regions of the plane where the « empty shape property » is satisfied.

We conclude there exists a data structure extending the « empty circle property » of the VD to more complex shapes. We defined mathematically this new structure and demonstrated its properties, along with its link with the VD.

These results suggest that our structure is applicable for speeding up algorithms which use plane geometric shapes, in the same way the VD speeds up algorithms which use points and distance measures.

To see my list of publications, Click Here.