sujet-these

Description

PhD thesis proposalProbabilistic methods for the efficiency of geometricstructures and algorithmsAdvisor: Olivier DevillersLocation: INRIA, BP 93, 06902 Sophia Antipolis cedex, FRANCEContact: Olivier Devillers 1 Context and motivationGeometric problems are central in many areas of science and engineering.Computational geometry, the study of combinatorial and algorithmic prob-lems in a geometric setting, and in particular triangulations have tremen-dous practical applications in areas such as computer graphics, computervision and imaging, scientific visualization, geographic information systems,astronomy, computational biology... Traditionally, the complexity of com-putational geometry algorithms is studied in the worst case setting. Thiskind of analysis is often quite pessimistic compared to real life data. Due tothe emergence of standardized software libraries, in particular the Compu-tational Geometry Algorithms Library CGAL, developed in the frameworkof an Open Source Project, the so-far mostly theoretical results developedin computational geometry are being used and extended for practical uselike never before. CGAL has been proposing efficient and robust packagescomputing Delaunay triangulations in the 2D and 3D Euclidean spaces foryears.2 ObjectivesThe goal of this research is to develop new probabilistic analysis for algo-rithms for convex hulls and triangulations. Such analysis should have con-sequences ...

Informations

• Publié par: Zaem
• Nombre de lectures: 6
• Langue: English

Extrait

PhD thesis proposal Probabilistic methods for the efficiency of geometric structures and algorithms Advisor: OlivierDevillers Location:INRIA, BP 93, 06902 Sophia Antipolis cedex, FRANCE Contact:Olivier Devillers <Olivier(dot)Devillers(at)sophia.inria.fr>

1 Contextand motivation Geometric problems are central in many areas of science and engineering. Computational geometry, the study of combinatorial and algorithmic prob- lems in a geometric setting, and in particular triangulations have tremen- dous practical applications in areas such as computer graphics, computer vision and imaging, scientific visualization, geographic information systems, astronomy, computational biology...Traditionally, the complexity of com- putational geometry algorithms is studied in the worst case setting.This kind of analysis is often quite pessimistic compared to real life data.Due to the emergence of standardized software libraries, in particular the Compu- tational Geometry Algorithms Library CGAL, developed in the framework of an Open Source Project, the so-far mostly theoretical results developed in computational geometry are being used and extended for practical use like never before.CGAL has been proposing efficient and robust packages computing Delaunay triangulations in the 2D and 3D Euclidean spaces for years.

2 Objectives The goal of this research is to develop new probabilistic analysis for algo- rithms for convex hulls and triangulations.Such analysis should have con- sequences on the design of triangulation algorithms.See more details in the work program below.

3 Knowledgeinvolved: (A good level in all these aspects is necessary.) mathematicalaspects (probability) algorithmic aspects C++ (templates, etc)

4 Collaborationsand funding The thesis will be co-advised by Pierre Calka (Univ.Rouen) and involve also some collaboration with INRIA-EPI Vegas.

1

The candidate will apply to usual grant for PhD students: — Ècole doctorale STIC http://edstic.i3s.unice.fr/ — INRIA CORDI Program http://www.inria.fr/institut/recrutement- metiers/offres/nos- offres- de- theses — An ANR project proposal (Prèsage) is currently submitted.

5 Workingprogram 5.1 Walksin triangulations Walks in triangulation are important components of triangulation algorithms. They are also of great interest in the mathematical field, notably in the con- text of first-passage percolation in random media.To locate a point in an existing triangulation, triangles are visited, starting from a known vertex, using neighborhood relations to get closer and closer to the query point. Walks come in various flavors depending on the choice of the starting point and the rules to go from a triangle to one of its neighbor.Some have been analyzed, other haven’t.

Analysis of walking algorithms.Walking in a triangulation is a basic technique of point location that can be used either alone, either in combi- nation with some strategies to choose the starting point of the walk.There exists several variants of walking techniques called straight walk, visibility walk or vertices walk [8].Only the straight walk has a correct analysis in 1/d the literature [9] and its cost isO(n)if the points are evenly distributed. We plan to attack the analysis of other kinds of walk.The straight walk is the easiest case to analyze because in that case, the involved simplices are independently characterized.

Design of walking strategies.To go further, in walking algorithms it remains several parameters to tune to complete the description of the algo- rithm. Asstated above, the visibility walk is non deterministic, thus there is still some choice in the algorithm, thus a better understanding of the behav- ior should allow to optimize the strategies -1- to choose in which neighboring simplex we have to go to continue the walk, -2- to choose the starting point from the walk (see[7] for some preliminary results).

Non euclidean spaces.In above items, boundary conditions could be a technical problem, thus a workaround to get still interesting results without d d boundary conditions is to work in periodic spaceR/Zalso called the flat torus in dimension d.Triangulations in periodic space are available in CGAL and have their own interest [5].Some other non Euclidean spaces will be studied such as spherical, hyperbolic or projective spaces [1, 4].

2

5.2 Smoothedcomplexity of convex hulls In a preliminary work [2], we analyzed the expected complexity of the con- vex hull of small perturbations of «regular» samples of a sphere in Rd, obtaining tight estimates of the average number of vertices as a function of n, d, the radius of perturbation.In other words, we started analyzing the smoothed complexity of convex hulls, a task that proved surprisingly non-trivial. Wepropose to extend this work in the following directions.

Faces of all dimension.Our preliminary work [2] only address the num- ber of extreme points under spherical noise.The number of faces of all dimensions can be attacked by the mean of higher degree probabilistic mo- ments.

Different perturbation models.Our preliminary work [2] use spherical noise in all dimensions and cubical noise only in 2D. Generalizing to other shapes of noise such as cubical noise in higher dimension or Gaussian noise is an interesting problem.Cubical and Gaussian noise have the property to alter the different coordinates in an independent way, this property is crucial in results of Damerow and Sohler [6] that provides sub optimal results for this kind of noise.

Extremal configurations.In [2] we consider an initial configuration, which is a good sample of a sphere, that is perturbed by some noise; then the expected number of extreme points is computed.For some noise inten- sity, we know some initial configuration with points inside the sphere where the expected number of extreme points is worse.Thus a natural question is what is the worse initial situation for a given level of noise ?

Smoothed complexity of Delaunay triangulationsThe real interest- ing stuff is Delaunay (as applications show a significant gap between worst- case and practical complexity).Comes as a natural follow-up after convex hulls as there are many connections...

alpha-shapes in 3D.first step as it interpolates be-Definition. Natural tween convex hull and Delaunay.To what extent do our technique for CH generalize to alpha-shapes?Quadratic configurations in 3D. Point sets can have quadratic DT in 3D but this requires them to essentially sit on a curve. Perturbing will therefore decrease the complexity as it will likely increase the «spread».Quantifiying the speed at which this decrease happens is an interesting question to understand whether noise explains why practical data never has quadratic-size DT. Do certain quadratic configurations have their complexity that decrease quicker than others?

3

Higher dimension, general bounds.Naturally, the big open problem is to identify all extremal configurations and analyze all their moments... Probably too much to ask, but we keep it as a long term goal.

References [1] MridulAanjaneya and Monique Teillaud.Triangulating the real projective plane. InMathematical Aspects of Computer and Information Sciences, 2007. . http://www- spiral.lip6.fr/MACIS2007/schedule.html [2] DominiqueAttali, Olivier Devillers, and Xavier Goaoc.The effect of noise on the number of extreme points.Research Report 7134, INRIA, 2009. . http://hal.inria.fr/inria- 00438409/ [3] P.Calka and T. Schreiber.Large deviation probabilities for the number of vertices of random polytopes in the ball.Adv. in Appl. Probab., 38:47–58, 2006. w.jstor.org/stable/20443 . http://ww 427 [4] Manuel Caroli, Pedro M. M. de Castro, SÉbastien Loriot, Olivier Rouiller, Monique Teillaud, and Camille Wormser.Robust and efficient Delaunay tri- angulations of points on or close to a sphere.In9th International Symposium on Experimental Algorithms, volume 6049 ofLecture Notes in Computer Sci- ence, pages 462–473, 2010. . http://hal.inria.fr/inria- 00405478/ [5] ManuelCaroli and Monique Teillaud.Computing 3d periodic triangulations. InEuropean Symposium on Algorithms, volume 5757 ofLecture Notes in Com- puter Science, pages 37–48, 2009. [6] ValentinaDamerow and Christian Sohler. Extreme points under random noise. InProc. 12th European Symposium on Algorithms, pages 264–274, 2004. . http://www.uni- paderborn.de/fachbereich/AG/agmadh/PapersPostscript/VIO_extreme_points_esa.ps.gz [7] PedroMachado Manhes de Castro and Olivier Devillers. Simple and efficient distribution-sensitive point location, in triangulations.InWorkshop on Algo- rithm Engineering and Experiments, 2011. . http://www.siam.org/proceedings/alenex/2011/ [8] OlivierDevillers, Sylvain Pion, and Monique Teillaud.Walking in a triangu- lation.Internat. J. Found. Comput. Sci., 13:181–199, 2002. . http://hal.inria.fr/inria- 00102194/ [9] LucDevroye, Christophe Lemaire, and Jean-Michel Moreau.Expected time analysis for Delaunay point location.Comput. Geom. Theory Appl., 29:61–89, 2004. . http://cg.scs.carleton.ca/~luc/CGTA63- final.pdf [10] The CGAL Project.CGAL User and Reference Manual. CGALEditorial Board, 3.7 edition, 2010. . http://www.cgal.org/Manual/3.7/doc_html/cgal_manual/packages.h%tml

4