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.
Paris - Biotech - Santé
29 Rue du Faubourg
Saint-Jacques
75014 Paris, France
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 number of photons. We provide a reference open source implementation.
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.
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 can be efficiently extracted from this data structure. We develop the above framework into an accurate and efficient clustering algorithm based on well-separated pair decompositions which outperforms earlier work in speed and/or quality for diffuse scenes.
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 by k-1 points; call such an algorithm a (k,k-1)-local search algorithm. Since then, local-search has turned out to be a powerful algorithmic approach towards achieving good approximation ratios for geometric problems (for geometric independent-set problem, for dominating sets, for the terrain guarding problem and several others). Unfortunately all these algorithms have the same limitation: local search is able to give a PTAS, but with large running times. In particular, the current best work shows that if k>=30, then local-search is able to give a constant factor (as a function of k) approximation ratio. Unfortunately this then implies that the running time for local-search to provably work at all is Ω(n^30) using the current framework. As currently local search is the only known method that gives approximation factors that could be useful in practice, it becomes important to explore the limits in both efficiency and quality of local search. Simple examples show that (1,0) and (2,1) local search cannot give constant factor approximations. In this paper, we show that, surprisingly, just (3,2) local search is able to give a constant-factor approximation; in fact we are able to get the precise quality limit of (3,2)-local search: factor 8 approximation. This simplest working instance of local search already gives an approximation factor that is better than all known other methods! In fact, our improvement applies to all algorithms that use local-search for geometric independent-set problem, for dominating sets, for the terrain guarding problem and several others. Finding efficient (3,2)-local search algorithms then becomes the key bottleneck in efficient and good-quality algorithms. In this paper we present such improved algorithms.
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 for disks in the plane. This constant factor depends on the sizes of epsilon-nets for disks; unfortunately, the current state-of-the-art bounds are large -- at least 24/epsilon and most likely larger than 40/epsilon. Thus the approximation factor of the Agarwal and Pan algorithm ends up being more than 40. The best lower-bound is 2/epsilon, which follows from the Pach-Woeginger construction for halfspaces in two dimensions. Thus there is a large gap between the best-known upper and lower bounds. Besides being of independent interest, finding precise bounds is important since this immediately implies an improved linear-time algorithm for the hitting-set problem. The main goal of this paper is to improve the upper-bound to 13.4/epsilon for disks in the plane. The proof is constructive, giving a simple algorithm that uses only Delaunay triangulations. We have implemented the algorithm, which is available as a public open-source module. Experimental results show that the sizes of epsilon-nets for a variety of data-sets is lower, around 9/epsilon.
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 algorithms have a severe limitation: local search gives a PTAS, but with hopeless running times; e.g., a 3-approximation takes more than n66 time for the geometric hitting set problem for disks in the plane. That leaves the question of whether a better analysis - both combinatorial and algorithmic - of local search can give a better approximation ratio in a more reasonable time. We show that this can indeed be done via a better understanding of the underlying geometric and combinatorial structure. We present tight approximation bounds for (3,2)-local search and give an (8 + &epsilon)-approximation algorithm with running time O(n2.34). Local search has turned out to be a powerful tool for certain geometric optimization problems and has been used to give a PTAS for a several problems: independent set of pseudodisks, dominating sets in disk intersection graphs, terrain guarding problem and several other problems. For all these problems our results show that (3,2) local search gives an 8-approximation and no better.
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 current epsilon-net constructions are large, so the approximation factor ends up being more than 40. Second, the algorithm uses sophisticated geometric tools and data structures with large resulting constants. These together have resulted in a lack of available software for fast computation of small hitting-sets. In this paper, we make progress on all three of these barriers: i) we prove improved bounds on sizes of epsilon-nets, ii) design hitting-set algorithms without the use of these data-structures and finally, iii) present dnet, a public source-code module that incorporates both these improvements
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
Website based on Skeleton. Copyright Norbert Bus, 2017
