Real-world data has a large geometric component, exhibiting significant geometric patterns.
Therefore exploiting the geometric nature of data to design efficient methods has became a very important topic in several scientific fields, e.g., computational geometry, discrete geometry, computer graphics, computer vision.
In this thesis we use geometric structures to design efficient algorithms for problems in two domains, computer graphics and combinatorial optimization.

Part I focuses on a geometric data structure called well-separated pair decomposition and its usage for one of the most challenging problems in computer graphics, namely efficient photo-realistic rendering.
One solution is the family of many-lights methods that approximate global illumination by individually computing illumination from a large number of virtual point lights (VPLs) placed on surfaces.
Considering each VPL individually results in a vast number of calculations. One successful strategy to reduce computations is to group the VPLs into a small number of clusters that are treated as individual lights with respect to each point to be shaded.
We use the well-separated pair decomposition of points as a basis for a data structure for pre-computing and compactly storing a set of view independent candidate VPL clusterings showing that a suitable clustering of the VPLs can be efficiently extracted from this data structure.
We show that instead of clustering points and/or VPLs independently, what is required is to cluster the product-space of the set of points to be shaded and the set of VPLs based on the induced pairwise illumination.
Additionally we propose an adaptive sampling technique to reduce the number of visibility queries for each product-space cluster.
Our method handles any light source that can be approximated with virtual point lights (VPLs), highly glossy materials and outperforms previous state-of-the-art methods.

Part II focuses on developing new approximation algorithms for a fundamental NP-complete problem in computational geometry. It focuses on the minimum hitting set problem, particularly on the case where given a set of points and a set of disks, we wish to compute the minimum-sized subset of the points that hits all disks.
It turns out that efficient algorithms for geometric hitting set rely on a key geometric structure, called epsilon-net.
We give an algorithm that uses only Delaunay triangulations to construct epsilon-nets of size 13.4/epsilon and we provide a practical implementation of a technique to calculate hitting sets in near-linear time using small sized epsilon-nets. Our results yield a 13.4 approximation for the hitting set problem with an algorithm that runs efficiently even on large data sets.
For smaller datasets, we present an implementation of the local search technique along with tight approximation bounds for its approximation factor, yielding an (8 + epsilon)-approximation algorithm with running time Õ(n^{2.34}).
Our work related to fundamental computational geometry problems also includes a novel dynamic convex hull algorithm for simple polygonal chains handling insertion or deletion of a point in amortized constant time.

The thesis can be downloaded in high resolution here (~120 MB) and as a compressed pdf here (~20 MB).

The thesis is based on the following publications:

__Global Illumination Using Well-Separated Pair Decomposition__(Norbert Bus, Nabil H. Mustafa, Venceslas Biri).

Computer Graphics Forum, to appear, 2015.__IlluminationCut__(Norbert Bus, Nabil H. Mustafa, Venceslas Biri).

Computer Graphics Forum (Proceedings of Eurographics) 2015.__Tighter Estimates for epsilon-nets for Disks__(Norbert Bus, Shashwat Garg, Nabil H. Mustafa, Saurabh Ray).

Computational Geometry: Theory and Applications, accepted, 2015.__Geometric Hitting Sets for Disks: Theory and Practice__(Norbert Bus, Nabil H. Mustafa, Saurabh Ray).

Proc. of the 23rd European Symposium on Algorithms (ESA) 2015.__Improved Local Search for Geometric Hitting Set Problems__(Norbert Bus, Shashwat Garg, Nabil H. Mustafa, Saurabh Ray).

Proc. of the 32st International Symposium on Theoretical Aspects of Computer Science (STACS) 2015.__Dynamic Convex Hull for Simple Polygonal Chains in Constant Amortized Time per Update__(Norbert Bus, Lilian Buzer).

Proc. of the 31th European Workshop on Computational Geometry (EUROCG) 2015.

See also my publications on HAL.

The source code accompanying the thesis can be obtained here:

__enet: library for computing small sized epsilon-nets__(Norbert Bus and Nabil Mustafa).

source code, readme.txt__IlluminationCut: efficient algorithm for global illumination__(Norbert Bus and Nabil Mustafa).

source code, readme.txt__giwspd: well-separated pairs for global illumination__(Norbert Bus and Nabil Mustafa).

source code, readme.txt__dnet: library for computing near-optimal hitting sets__(Norbert Bus and Nabil Mustafa).

source code, readme.txt

My list of presentations:

__IlluminationCut.__

Eurographics, Zurich, 2015.__Compact Geometric Structures in Graphics.__

Journees Informatique et Geometrique, Paris, 2015.__Improved Local-Search for Geometric Hitting Sits.__

Symposium on Theoretical Aspects of Computer Science (STACS), Munich, 2015.__The Use of Geometric Structures for Computer Graphics and Optimization.__

VirtaMed, Zurich, 2015.__Approximation Algorithms for Independent Set/Hitting Set of Non-Piercing Rectangles via Local-Search.__

International Symposium of Mathematical Programming (ISMP), Pittsburgh, 2015.__Dynamic Convex Hull for Simple Polygonal Chains in Constant Time per Update.__

European Workshop on Computational Geometry (EuroCG), Ljubljana, 2015.__Geometric Hitting Sets for Disks: Theory and Practice.__

European Symposium on Algorithms (ESA), Patras, 2015.__Hitting Sets for Disks via Local-Search.__

ESIEE, Paris, 2014.__Improved Algorithm for Hitting Sets.__

Recent Advances in Linear Optimization (RALO), Paris, 2014.__Light Clustering for Photorealistic Rendering__

Journee du Groupe de Travail de Geometrie Discrete, Paris, 2013.__Light Clustering Using Well-Separated Pair Decompositions__

ESIEE, Paris, 2013.