[. Bibliography, U. Ashok, S. Azmi, and . Govindarajan, Small strong epsilon nets, In: Comput. Geom, vol.47, issue.9, pp.899-909, 2014.

[. Acharyya, M. Basappa, and G. K. Das, Unit Disk Cover Problem in 2D, English. In: Computational Science and Its Applications -ICCSA 2013, pp.73-85, 2013.
DOI : 10.1007/978-3-642-39643-4_6

[. Afshani and T. M. Chan, Optimal Halfspace Range Reporting in Three Dimensions, pp.180-186, 2009.
DOI : 10.1137/1.9781611973068.21

[. Ambühl, T. Erlebach, M. Mihalák, and M. Nunkesser, Constant-Factor Approximation for Minimum-Weight (Connected) Dominating Sets in Unit Disk Graphs, In: APPROX-RANDOM, pp.3-14, 2006.
DOI : 10.1007/11830924_3

K. Pankaj, E. Agarwal, M. Ezra, and . Sharir, Near-Linear Approximation Algorithms for Geometric Hitting Sets, In: Algorithmica, vol.63, issue.12, pp.2012-2013

[. Arya, N. Garg, R. Khandekar, A. Meyerson, K. Munagala et al., Local search heuristic for k-median and facility location problems, In: STOC, pp.21-29, 2001.

[. Aronov and S. Har-peled, On Approximating the Depth and Related Problems, SIAM Journal on Computing, vol.38, issue.3, pp.899-921, 2008.
DOI : 10.1137/060669474

K. Pankaj, N. H. Agarwal, and . Mustafa, Independent set of intersection graphs of convex objects in 2D, In: Comput. Geom, vol.34, issue.2, pp.83-95, 2006.

K. Pankaj, J. Agarwal, and . Pan, Near-Linear Algorithms for Geometric Hitting Sets and Set Covers, Symposium on Computational Geometry, p.271, 2014.

K. Pankaj, J. Agarwal, M. Pach, and . Sharir, State of the Union (of Geometric Objects): A Review, 2007.

N. Bus and L. Buzer, Dynamic Convex Hull for Simple Polygonal Chains in Constant Amortized Time per Update, Proceedings of the 31th European Workshop on Computational Geometry (EUROCG), 2015.

T. Bodt and P. Dutré, Coherent Lightcuts, 2008.

[. Billen, B. Engelen, A. Lagae, and P. Dutré, Probabilistic Visibility Evaluation for Direct Illumination, Proceedings of Eurographics Symposium on Rendering 2013), pp.2013-2052
DOI : 10.1111/cgf.12149
URL : https://lirias.kuleuven.be/bitstream/123456789/401248/1/paper1023.pdf

[. Brönnimann and M. T. Goodrich, Almost optimal set covers in finite VC-dimension, Discrete & Computational Geometry, vol.16, issue.2, pp.463-479, 1995.
DOI : 10.1007/BF02570718

[. Bus, S. Garg, N. H. Mustafa, and S. Ray, Improved Local Search for Geometric Hitting Set, 32st International Symposium on Theoretical Aspects of Computer Science (STACS), 2015.
URL : https://hal.archives-ouvertes.fr/hal-01188990

[. Bus, S. Garg, N. H. Mustafa, and S. Ray, Tighter Estimates for epsilon-nets for Disks, In: Computational Geometry: Theory and Applications, vol.53, 2016.

S. Gerth, R. Brodal, and . Jacob, Dynamic Planar Convex Hull, pp.617-626, 2002.

[. Bus, N. H. Mustafa, and V. Biri, Global Illumination Using Well-Separated Pair Decomposition, Computer Graphics Forum, vol.31, issue.4, p.2015
DOI : 10.1111/cgf.12610
URL : https://hal.archives-ouvertes.fr/hal-01188993

[. Bus, N. H. Mustafa, and V. Biri, IlluminationCut, Proceedings of Eurographics 2015, p.2015
DOI : 10.1111/cgf.12584
URL : https://hal.archives-ouvertes.fr/hal-01188989

[. Bus, N. H. Mustafa, and S. Ray, Geometric Hitting Sets for Disks: Theory and Practice, 23rd European Symposium on Algorithms (ESA)
DOI : 10.1007/978-3-662-48350-3_75
URL : https://hal.archives-ouvertes.fr/hal-01188987

[. Claude, G. K. Das, R. Dorrigiv, S. Durocher, R. Fraser et al., AN IMPROVED LINE-SEPARABLE ALGORITHM FOR DISCRETE UNIT DISK COVER, Discrete Mathematics, Algorithms and Applications, vol.02, issue.01, pp.77-88, 2010.
DOI : 10.1142/S1793830910000486

[. Chazelle and J. Friedman, A deterministic view of random sampling and its use in geometry, Combinatorica, vol.16, issue.3, pp.229-249, 1990.
DOI : 10.1007/BF02122778

T. M. Chan, Optimal output-sensitive convex hull algorithms in two and three dimensions, Discrete & Computational Geometry, vol.6, issue.4, pp.361-368, 1996.
DOI : 10.1007/BF02712873

M. Timothy, S. Chan, and . Har-peled, Approximation algorithms for maximum independent set of pseudo-disks, Symposium on Computational Geometry, pp.333-340, 2009.

H. Per and . Christensen, Point-Based Approximate Color Bleeding, 2008.

B. Paul, S. Callahan, and . Kosaraju, A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential fields, In: J. ACM, vol.42, issue.1, pp.67-90, 1995.

P. Carmi, M. J. Katz, and N. Lev-tov, Covering Points by Unit Disks of Fixed Location, pp.644-655, 2007.
DOI : 10.1007/978-3-540-77120-3_56

C. Gruia, I. I. Alinescu, . Mandoiu, A. Peng-jun-wan, and . Zelikovsky, Selecting Forwarding Neighbors in Wireless Ad Hoc Networks, pp.101-111, 2004.

K. Gautam, R. Das, A. Fraser, B. G. López-ortiz, and . Nickerson, On the Discrete Unit Disk Cover Problem, In: International Journal on Computational Geometry and Applications, vol.22, issue.5, pp.2012-407

T. Davidovi?, J. K?ivánek, M. Ha?an, P. Slusallek, and K. Bala, Combining global and local virtual lights for detailed glossy illumination, ACM Transactions on Graphics, vol.29, issue.6, pp.1-1438, 2010.
DOI : 10.1145/1882261.1866169

C. Dachsbacher, J. K?ivánek, M. Ha?an, A. Arbree, B. Walter et al., Scalable Realistic Rendering with Many-Light Methods, Eurographics 2013 ? State of the Art Reports, pp.23-38, 2013.
DOI : 10.1111/cgf.12256

[. Dammertz, A. Keller, and H. Lensch, Progressive Point-Light-Based Global Illumination, Computer Graphics Forum, vol.26, issue.2, pp.2504-2515, 2010.
DOI : 10.1111/j.1467-8659.2010.01786.x
URL : http://nbn-resolving.de/urn:nbn:de:bsz:289-vts-76179

E. D. Demaine and M. Patrascu, Tight bounds for dynamic convex hull queries (again), Proceedings of the twenty-third annual symposium on Computational geometry , SCG '07, pp.354-363, 2007.
DOI : 10.1145/1247069.1247131

B. Michael, W. D. Dillencourt, and . Smith, Graph-theoretical conditions for inscribability and Delaunay realizability, In: Discrete Mathematics, vol.16113, pp.63-77, 1996.

E. Ezra, D. Halperin, and M. Sharir, Speeding up the incremental construction of the union of geometric objects in practice, Computational Geometry, vol.27, issue.1, pp.63-85, 2004.
DOI : 10.1016/j.comgeo.2003.07.006

D. [. Even, S. Rawitz, and . Shahar, Hitting sets when the VC-dimension is small, Information Processing Letters, vol.95, issue.2, pp.358-362, 2005.
DOI : 10.1016/j.ipl.2005.03.010

R. Frederickx, P. Bartels, and P. Dutré, Adaptive LightSlice for Virtual Ray Lights In: EG 2015 ? Short Papers, pp.61-64, 2015.

R. Fraser, Algorithms for Geometric Covering and Piercing Problems, 2012.

. Gan11, K. Shashidhara, and . Ganjugunte, Geometric Hitting Sets and Their Variants, 2011.

I. Gargantini, An effective way to represent quadtrees, Communications of the ACM, vol.25, issue.12, pp.905-910, 1982.
DOI : 10.1145/358728.358741

D. [. Garey and . Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, 1979.

I. Georgiev, J. K?ivánek, S. Popov, and P. Slusallek, Importance Caching for Complex Illumination, Computer Graphics Forum, vol.0, issue.7-9, pp.2012-2012
DOI : 10.1111/j.1467-8659.2012.03049.x
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.232.3849

R. L. Graham, An efficient algorith for determining the convex hull of a finite planar set, Information Processing Letters, vol.1, issue.4, pp.132-133, 1972.
DOI : 10.1016/0020-0190(72)90045-2

[. Georgiev and P. Slusallek, Simple and Robust Iterative Importance Sampling of Virtual Point Lights, Proceedings of Eurographics, 2010.

Y. Han, Deterministic Sorting in O(n log log n) Time and Linear Space, Proceedings of the Thirty-fourth Annual ACM Symposium on Theory of Computing, pp.602-608, 2002.

H. Har-peled, M. Kaplan, S. Sharir, and . Smorodinsky, Epsilon- Nets for Halfspaces Revisited, 1410.

M. Ha?an, J. K?ivánek, B. Walter, and K. Bala, Virtual spherical lights for many-light rendering of glossy scenes, ACM Transactions on Graphics, vol.28, issue.5, pp.1-143, 2009.
DOI : 10.1145/1618452.1618489

S. Dorit, W. Hochbaum, and . Maass, Approximation Schemes for Covering and Packing Problems in Image Processing and VLSI, In: J. ACM, vol.32, issue.1, pp.130-136, 1985.

W. [. Hochbaum and . Maass, Fast approximation algorithms for a nonconvex covering problem, Journal of Algorithms, vol.8, issue.3, pp.305-323, 1987.
DOI : 10.1016/0196-6774(87)90012-5

. Har-peled, Constructing Planar Cuttings in Theory and Practice, SIAM Journal on Computing, vol.29, issue.6
DOI : 10.1137/S0097539799350232

[. Ha?an, F. Pellacini, and K. Bala, Matrix row-column sampling for the many-light problem, In: ACM Trans. Graph, vol.26, issue.3, 2007.

[. Holländer, T. Ritschel, E. Eisemann, and T. Boubekeur, ManyLoDs: Parallel Many-View Level-of-Detail Selection for Real-Time Global Illumination, Proceedings of the 22nd Eurographics Conference on Rendering, pp.1233-1240, 2011.
DOI : 10.1111/j.1467-8659.2011.01982.x

[. Ha?an, E. Velázquez-armendariz, F. Pellacini, and K. Bala, Tensor Clustering for Rendering Many-Light Animations, Proceedings of the Nineteenth Eurographics Conference on Rendering, pp.1105-1114, 2008.
DOI : 10.1111/j.1467-8659.2008.01248.x

D. Haussler and E. Welzl, Epsilon-nets and simplex range queries, Proceedings of the second annual symposium on Computational geometry , SCG '86, pp.127-151, 1987.
DOI : 10.1145/10515.10522
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.136.5314

. Henrik-wann-jensen, Realistic image synthesis using photon mapping, 2001.

J. T. Kajiya, The Rendering Equation, Proceedings of the 13th Annual Conference on Computer Graphics and Interactive Techniques, pp.143-150, 1986.

]. R. Kar72 and . Karp, Reducibility Among Combinatorial Problems, In: Complexity of Computer Computations, pp.85-103, 1972.

]. N. Kar84 and . Karmarkar, A New Polynomial-time Algorithm for Linear Programming, Proceedings of the Sixteenth Annual ACM Symposium on Theory of Computing, pp.302-311, 1984.

A. Keller, Instant radiosity, Proceedings of the 24th annual conference on Computer graphics and interactive techniques , SIGGRAPH '97, pp.49-56, 1997.
DOI : 10.1145/258734.258769

[. K?ivánek, J. A. Ferwerda, and K. Bala, Effects of global illumination approximations on material appearance, 2010. SIGGRAPH '10, pp.1-11210
DOI : 10.1145/1778765.1778849

J. K?ivánek, M. Ha?an, A. Arbree, C. D. , A. Keller et al., Optimizing Realistic Rendering with Many-Light Methods, SIGGRAPH 2012 Course, 2012.

T. Kollig and A. Keller, Illumination in the Presence of Weak Singularities, pp.245-257, 2004.
DOI : 10.1007/3-540-31186-6_15

[. Klee and G. J. Minty, How good is the simplex algorithm?, In: Inequalities, vol.III, pp.159-175, 1972.

[. Kanungo, D. M. Mount, N. S. Netanyahu, C. D. Piatko, R. Silverman et al., A local search approximation algorithm for k-means clustering, Symposium on Computational Geometry, pp.10-18, 2002.

L. Lin and Y. Jiang, The computation of hitting sets: Review and new algorithms, Information Processing Letters, vol.86, issue.4, pp.177-184, 2003.
DOI : 10.1016/S0020-0190(02)00506-9

[. Lakshmi and M. Neelima, Maximising Wireless sensor Network life time through cluster head selection using Hit sets, In: International Journal of Computer Science Issues, 2012.

S. Laine, H. Saransaari, J. Kontkanen, J. Lehtinen, and T. Aila, Incremental Instant Radiosity for Real-Time Indirect Illumination, Proceedings of Eurographics Symposium on Rendering, pp.277-286, 2007.

P. Eric, Y. D. Lafortune, and . Willems, Bi-Directional Path Tracing, Proceedings of the 3rd International Conference on Graphics and Visualization Techniques (COMPUGRAPHICS '93, pp.145-153, 1993.

]. J. Mat02 and . Matousek, Lectures in Discrete Geometry, 2002.

J. Matousek, On Constants for Cuttings in the Plane, Discrete & Computational Geometry, vol.20, issue.4, pp.427-448, 1998.
DOI : 10.1007/PL00009394

A. A. Melkman, On-line construction of the convex hull of a simple polyline, Information Processing Letters, vol.25, issue.1, pp.11-12, 1987.
DOI : 10.1016/0020-0190(87)90086-X

[. Miksik, Implementing Lightcuts, In: CESCG, 2010.

H. Nabil, S. Mustafa, and . Ray, Improved Results on Geometric Hitting Set Problems, In: Discrete & Computational Geometry, vol.44, issue.4, pp.883-895, 2010.

[. Novák, D. Nowrouzezahrai, C. Dachsbacher, and W. Jarosz, Progressive Virtual Beam Lights, Computer Graphics Forum, vol.2006, issue.1, p.2012
DOI : 10.1111/j.1467-8659.2012.03136.x

J. Novák, D. Nowrouzezahrai, C. Dachsbacher, and W. Jarosz, Virtual ray lights for rendering scenes with participating media, Proceedings of SIGGRAPH), p.2012
DOI : 10.1145/2185520.2185556

J. Ou and F. Pellacini, LightSlice: matrix slice sampling for the manylights problem, In: ACM Trans. Graph, vol.30, issue.6, p.179, 2011.

[. Ottmann, P. Widmayer, and D. Wood, A fast algorithm for the Boolean masking problem, Computer Vision, Graphics, and Image Processing, vol.30, issue.3, pp.249-268, 1985.
DOI : 10.1016/0734-189X(85)90159-8

P. [. Pach and . Agarwal, Combinatorial Geometry, 1995.
DOI : 10.1002/9781118033203
URL : http://dx.doi.org/10.1016/0898-1221(96)87331-7

. Muller, Irregular Grain Structure in Micromagnetic Simulation, In: Journal of Applied Physics, vol.79, pp.4694-4696, 1996.

S. Popov, I. Georgiev, P. Slusallek, and C. Dachsbacher, Adaptive Quantization Visibility Caching, Proceedings of Eurographics 2013, p.2013
DOI : 10.1111/cgf.12060

[. Prutkin, A. Kaplanyan, and C. Dachsbacher, Reflective Shadow Map Clustering for Real-Time Global Illumination, Eurographics (Short Papers ). 2012, pp.9-12

E. Paquette, P. Poulin, and G. Drettakis, A Light Hierarchy for Fast Rendering of Scenes with Many Lights, Computer Graphics Forum, vol.17, issue.3, pp.63-74, 1998.
DOI : 10.1111/1467-8659.00254
URL : https://hal.archives-ouvertes.fr/inria-00510080

E. Pyrga and S. Ray, New existence proofs for epsilon-nets, Proceedings of Symposium on Computational Geometry, pp.199-207, 2008.

J. Pach and M. Sharir, Combinatorial Geometry with Algorithmic Applications ? The Alcala Lectures, 2006.

P. Franco, M. I. Preparata, and . Shamos, Computational Geometry: An Introduction, 1985.

G. [. Pach and . Woeginger, Some new bounds for Epsilon-nets, Proceedings of the sixth annual symposium on Computational geometry , SCG '90, pp.10-15, 1990.
DOI : 10.1145/98524.98529

I. Radax, Instant Radiosity for Real-Time Global Illumination, 2008.

[. Ritschel, T. Grosch, M. H. Kim, H. Seidel, C. Dachsbacher et al., Imperfect Shadow Maps for Efficient Computation of Indirect Illumination, Proc. of SIGGRAPH, 2008.

M. [. Raz and . Safra, A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing , STOC '97, pp.475-484, 1997.
DOI : 10.1145/258533.258641

H. Samet, Spatial Data Structures In: Modern Database Systems, pp.361-385, 1995.

[. Simon, J. Hanika, and C. Dachsbacher, Rich-VPLs for Improving the Versatility of Many-Light Methods, Proceedings of Eurographics 2015, pp.2015-575
DOI : 10.1111/cgf.12585

[. Shewchuk, Tetrahedral mesh generation by Delaunay refinement, Proceedings of the fourteenth annual symposium on Computational geometry , SCG '98, pp.86-95, 1998.
DOI : 10.1145/276884.276894
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.41.2243

[. Segovia, J. Iehl, B. Mitanchey, and . Péroche, Bidirectional Instant Radiosity, In: EGSR, pp.389-398, 2006.

[. Segovia, J. Iehl, and B. Péroche, Metropolis Instant Radiosity, Computer Graphics Forum, vol.26, issue.3, pp.425-434, 2007.
DOI : 10.1111/j.1467-8659.2007.01065.x
URL : https://hal.archives-ouvertes.fr/hal-01501494

K. [. Silva, S. S. Panetta, and . Agaian, Quantifying image similarity using measure of enhancement by entropy, Mobile Multimedia/Image Processing for Military and Security Applications 2007, 2007.
DOI : 10.1117/12.720087

[. Tatarchuk, Advances in real-time rendering in 3D graphics and games I, ACM SIGGRAPH 2009 Courses on, SIGGRAPH '09, 2009.
DOI : 10.1145/1667239.1667243

E. Veach and L. Guibas, Bidirectional Estimators for Light Transport, English. In: Photorealistic Rendering Techniques, pp.145-167, 1995.
DOI : 10.1007/978-3-642-87825-1_11
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.641.5864

E. Veach and L. J. Guibas, Metropolis light transport, Proceedings of the 24th annual conference on Computer graphics and interactive techniques , SIGGRAPH '97, pp.65-76, 1997.
DOI : 10.1145/258734.258775
URL : http://cdserver.icemt.iastate.edu/cd/s97cp/contents/papers/veach/metro.pdf

A. Vinterbo and . Øhrn, Minimal approximate hitting sets and rule templates, International Journal of Approximate Reasoning, vol.25, issue.2, pp.123-143, 2000.
DOI : 10.1016/S0888-613X(00)00051-7
URL : http://doi.org/10.1016/s0888-613x(00)00051-7

B. Walter, A. Arbree, K. Bala, and D. P. Greenberg, Multidimensional lightcuts, In: ACM SIGGRAPH, pp.1081-1088, 2006.

I. Wald, On fast Construction of SAH-based Bounding Volume Hierarchies, 2007 IEEE Symposium on Interactive Ray Tracing, pp.33-40, 2007.
DOI : 10.1109/RT.2007.4342588

[. Wu and Y. Chuang, VisibilityCluster: Average Directional Visibility for Many-Light Rendering, In: Visualization and Computer Graphics IEEE Transactions on, vol.19, issue.9, pp.2013-1566

B. Walter, S. Fernandez, A. Arbree, K. Bala, M. Donikian et al., Lightcuts, ACM Transactions on Graphics, vol.24, issue.3, pp.1098-1107, 2005.
DOI : 10.1145/1073204.1073318

S. Woop, L. Feng, I. Wald, and C. Benthin, Embree ray tracing kernels for CPUs and the Xeon Phi architecture, ACM SIGGRAPH 2013 Talks on, SIGGRAPH '13, p.2013
DOI : 10.1145/2504459.2504515

B. Walter, P. Khungurn, and K. Bala, Bidirectional lightcuts, ACM Transactions on Graphics, vol.31, issue.4, pp.1-5911, 2012.
DOI : 10.1145/2185520.2185555

[. Wald, T. J. Purcell, J. Schmittler, C. Benthin, and P. Slusallek, Realtime Ray Tracing and its use for Interactive Global Illumination, Eurographics State of the Art Reports, 2003.

I. Wald, S. Woop, C. Benthin, G. S. Johnson, and M. Ernst, Embree, ACM Transactions on Graphics, vol.33, issue.4, pp.1-1438, 2014.
DOI : 10.1145/2601097.2601199

G. Wang, G. Xie, and W. Wang, Efficient search of lightcuts by spatial clustering, SIGGRAPH Asia 2011 Sketches on, SA '11, pp.1-26, 2011.
DOI : 10.1145/2077378.2077411