Norbert Bus, PhD

Research engineer

Profile picture

Norbert Bus, PhD

Research engineer

I hold a MSc degree in mathematics from Budapest University of Technology and a PhD from Université Paris-Est in computer science. I was previously working as a postdoc in the computer graphics group of Tamy Boubekeur at Télécom ParisTech. Currently I am a research engineer at TheraPanacea led by Nikos Paragios, working on efficient algorithms for adaptive radiotherapy.

You can find my CV here.

 

Address

Paris - Biotech - Santé
29 Rue du Faubourg Saint-Jacques
75014 Paris, France

Email

norbert.bus@ecp.fr

Other
View Norbert Bus's profile on LinkedIn View Norbert Bus's profile on dblp.

Publications

Double Hierarchies for Directional Importance Sampling in Monte Carlo Rendering

Abstract

We describe a novel representation of the light field tailored to improve importance sampling for Monte Carlo rendering. The domain of the light field i.e., the product space of spatial positions and directions is hierarchically subdivided into subsets on which local models characterize the light transport. The data structure, that is based on double trees, approximates the exact light field and enables very efficient queries for importance sampling and easy tracing of photons in the scene. The framework is simple yet flexible, enabling the usage of any type of local model for representing the light field, provided it can be efficiently importance sampled. The method also supports progressive refinement with an arbitrary numbe...
more

IlluminationCut

Abstract

We present a novel algorithm, IlluminationCut, for rendering images using the many-lights framework. It handles any light source that can be approximated with virtual point lights (VPLs) as well as highly glossy materials. The algorithm extends the Multidimensional Lightcuts technique by effectively creating an illumination-aware clustering of the product-space of the set of points to be shaded and the set of VPLs. Additionally, the number of visibility queries for each product-space cluster is reduced by using an adaptive sampling technique. Our framework is flexible and achieves around 3-6 times speedup over previous state-of-the-art methods.

Global Illumination Using Well-Separated Pair Decomposition

Abstract

Instant radiosity methods rely on using a large number of virtual point lights (VPLs) to approximate global illumination. Efficiency considerations require grouping the VPLs into a small number of clusters that are treated as individual lights with respect to each point to be shaded. Two examples of clustering algorithms are Lightcuts and LightSlice. In this work we use the notion of geometric separatedness of point sets as a basis for a data structure for pre-computing and compactly storing a set of candidate VPL clusterings. Our data structure is created prior to rendering, is view-independent and relies only on geometric and radiometric information. For any point to be shaded, we show that a suitable clustering of the VPLs c...
more

Limits of Local Search: Quality and Efficiency

Abstract

Over the past several decades there has been steady progress towards the goal of polynomial-time approximation schemes (PTAS) for fundamental geometric combinatorial optimization problems. A foremost example is the geometric hitting set problem: given a set P of points and a set D of geometric objects, compute the minimum-sized subset of P that hits all objects in D. For the case where D is a set of disks in the plane, the 30-year quest for a PTAS, starting from the seminal work of Hochbaum, was finally achieved in 2010. Surprisingly, the algorithm to achieve the PTAS is simple: local-search. In particular, the algorithm starts with any hitting set, and iteratively tries to decrease its size by trying to replace some k points b...
more


Limits of local search: quality and efficiency
Additional resources

Paper
BibTex

Tighter Estimates for epsilon-nets for Disks

Abstract

The geometric hitting set problem is one of the basic geometric combinatorial optimization problems: given a set P of points, and a set D of geometric objects in the plane, the goal is to compute a small-sized subset of P that hits all objects in D. In 1994, Bronniman and Goodrich made an important connection of this problem to the size of fundamental combinatorial structures calledepsilon-nets, showing that small-sized epsilon-nets imply approximation algorithms with correspondingly small approximation ratios. Very recently, Agarwal and Pan showed that their scheme can be implemented in near-linear time for disks in the plane. Altogether this gives O(1)-factor approximation algorithms in O(n polylog n) time for hitting sets fo...
more


Tighter estimates for epsilon-nets
Additional resources

Preprint
Source code
BibTex

Improved Local Search for Geometric Hitting Set Problems

Abstract

Over the past several decades there has been steady progress towards the goal of polynomial-time approximation schemes (PTAS) for fundamental geometric combinatorial optimization problems. A foremost example is the geometric hitting set problem: given a set P of points and a set D of geometric objects, compute the minimum-sized subset of P that hits all objects in D. For the case where D is a set of disks in the plane, the 30-year quest for a PTAS, starting from the seminal work of Hochbaum-Mass, was finally achieved by Mustafa-Ray. Surprisingly, the algorithm to achieve the PTAS is simple: local-search. Since then, several open problems on PTAS have been resolving using similar analysis by local-search. Unfortunately these alg...
more


Improved local search
Additional resources

Paper
BibTex

Geometric Hitting Sets for Disks: Theory and Practice

Abstract

The geometric hitting set problem is one of the basic geometric combinatorial optimization problems: given a set P of points, and a set D of geometric objects in the plane, the goal is to compute a small-sized subset of P that hits all objects in D. In 1994, Bronniman and Goodrich made an important connection of this problem to the size of fundamental combinatorial structures called epsilon-nets, showing that small-sized epsilon-nets imply approximation algorithms with correspondingly small approximation ratios. Finally, recently Agarwal and Pan showed that their scheme can be implemented in near-linear time for disks in the plane. This current state-of-the-art is lacking in three ways. First, the constants in c...
more


Efficient epsilon-net construction.
Additional resources

Paper
Source code (dnet)
BibTex

Dynamic Convex Hull for Simple Polygonal Chains in Constant Amortized Time per Update

Abstract

We present a new algorithm to construct a dynamic convex hull in the Euclidean plane, supporting insertion and deletion of points. Both operations require amortized constant time. At each step the complete representation of the convex hull is accessible. The algorithm is on-line, does not require prior knowledge of all the points. The only assumptions are that the points have to be located on a simple polygonal chain and that the insertions and deletions must be carried out in the order induced by the polygonal chain.i


Dynamic convex hull, Melkman
Additional resources

Paper
BibTex


Website based on Skeleton. Copyright Norbert Bus, 2017