Thesis

The Use of Geometric Structures in Graphics and Optimization

Abstract

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 Õ(n2.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.

Manuscript:

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

Publications:

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.

Software:

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
Talks:

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.