, 15 3.3 L'approche mariage avant conquute TriMariage(A) pour trier A, p.16
, On suppose min n i=1 D i = 0, p.28
, A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra, et Fukuda
, Reverse Search for Enumeration Rapport technique n No. 92-5, Tsukuba University, Graduate School of Systems Management EEcient parallel solutions to some geometric problems, J. Parallel Distrib. Comput, vol.3, p.4922507, 1986.
, Intersection and decomposition algorithms for planar arrangements, 1991.
, Optimalwork parallel algorithms for higher-dimensional convex hulls, SIAM, p. Proc. 6th ACM Symp. on Disc. Alg
DOI : 10.1109/sfcs.1994.365724
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.114.749
, The Design and Analysis of Computer Algorithms, 1974.
, Data Structures and Algorithms, 1983.
, Parallel Sorting Algorithms, p.229, 1985.
, Helly theorems and generalized linear programming, Proc. 9th Annu. ACM Sympos, p.63372
, Helly-type theorems and generalized linear programming On computing Voronoi diagrams by divide-prune-and-conquer, AR96] Amato (Nancy M.) et Ramos Proc. 12th Annu. ACM Sympos, pp.2411261-1666175, 1994.
, Circle shooting in a simple polygon, 1990.
, Circle shooting in a simple polygon, J. Algorithms, vol.14, p.69987, 1993.
, The probabilistic method Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences, J. Wiley & Sons J. Combin. Theory Ser. A, vol.52, issue.2, p.2288274, 1989.
, A fast convex hull algorithm, Information Processing Letters, vol.7, issue.5, p.2199222, 1978.
DOI : 10.1016/0020-0190(78)90003-0
, An optimal algorithm for nding segment intersections, Proc. 11th Annu. ACM Sympos, p.2111219
, Output-sensitive construction of the 3-d Delaunay triangulation of constrained sets of points, CCrrzo (A.), Devillers (O.) et Teillaud, 1991.
, Output-sensitive construction of the 3-d Delaunay triangulation of constrained sets of points, CCrrzo (A.), Devillers (O.) et Teillaud Proc. 3rd Canad. Conf. Comput. Geom, p.1100113
, OUTPUT SENSITIVE CONSTRUCTION OF THE DELAUNAY TRIANGULATION OF POINTS LYING IN TWO PLANES, CCrrzo (A.), Devillers (O.) et Teillaud, p.1114, 1996.
DOI : 10.1142/S0218195996000022
URL : https://hal.archives-ouvertes.fr/hal-00795075
, A New Linear Convex Hull Algorithm for Simple Polygons, IEEE Transactions on Information Theory, vol.30, issue.84
, GGommtrie 3. convexes et polytopes, polyydres rrguliers, aires et volumes, 1974.
, Time bounds for selection Almost optimal set covers in nite VC-dimension, Proc. 10th Annu. ACM Sympos, p.2933302, 1972.
, Efcient probabistically checkable proofs and applications to approximation Compliant motion planning with geometric models, Proc. 25th Annu. Symp. Theory Comput. Proc. 3rd Annu. ACM Sympos. Comput. Geom., pp. 1711180. BK91] Bajaj (C.) et Kim (M. S.). Convex hull of objects bounded by algebraic curves. Algorithmica, pp.294-304, 1991.
, Voronoi (Thiessen) Polygons Geometric transforms for fast geometric algorithms, Dept. Comput. Sci, 1980.
, An Introduction to Convex Polytopes, 1983.
, Derandomization of geometric algorithms, 1995.
, GGommtrie algorithmique, 1995.
, GGommtrie algorithmique. Paris, Ediscience international An optimal algorithm for intersecting line segments in the plane An optimal algorithm for intersecting line segments in the plane, CE88] Chazelle (B.) et Edelsbrunner Proc. 29th Annu. IEEE Sympos. Found. Comput. Sci., pp. 5900600. CE92] Chazelle (B.) et Edelsbrunner, p.1154, 1992.
, A deterministic view of random sampling and its use in geometry A deterministic view of random sampling and its use in geometry, Proc. 29th Annu, pp.5399549-2299249, 1990.
, On the convex layers of a planar set, IEEE Trans. Inform. Theory, pp.31-5099517, 1985.
, An optimal convex hull algorithm for point sets in any xed dimension, Comput. Sci, 1991.
, Output-Sensitive Results on Convex Hulls, Extreme Points, and Related Problems, Proc. of the A.C.M. Symp. on Computational Geometry, 1995.
, Output-sensitive results on convex hulls, extreme points, and related problems, Proc. 11th Annu. ACM Sympos, p.10019
, Fixed-dimensional linear programming queries made easy, Proc. 12th Annu. ACM Sympos, p.2844290
, CG Impact Task Force Report, Report, p.96
, Parallel algorithms for geometric problems A greedy heuristic for the set-covering problem An algorithm for convex polytopes, CK70] Chand (D. R.) et Kapur (S. S.), pp.2333235-78886, 1970.
, Further applications of random sampling to computational geometry, Proc. 18th Annu. ACM Sympos. Theory Comput, p.4144423
, A Las Vegas algorithm for linear programming when the dimension is small, Proc. 29th Annu. IEEE Sympos. Found. Comput. Sci, p.4522456
, Introduction to Algorithms Derandomizing an Output- Sensitive Convex Hull Algorithm in Three Dimensions Rapport technique On linear-time deterministic algorithms for optimization problems in xed dimension Derandomizing an output-sensitive convex hull algorithm, CM92] Chazelle (B.) et Matouuek (J.) CM93] Chazelle (B.) et Matouuek (J.) Proc. 4th ACM-SIAM Sympos. Discrete Algorithms CM94] Chazelle (Bernard) et Matou sek Proceedings of CG- TA'94, pp.2811-290, 1990.
, Probabilistic Analysis of Packing and Partitionning Algorithms Algorithms for diametral pairs and convex hulls that are optimal, randomized, and incremental, Proc. 4th Annu. ACM Sympos, p.12217, 1988.
, Applications of random sampling in computational geometry, II. Discrete Comput. Geom, vol.4, p.3877421, 1989.
, EEcient parallel algorithms for geometric kclustering problems EEcient algorithms for ray shooting and hidden surface removal On the oscillation of the expected number of points on a random convex hull Scalable algorithms for bichromatic line segment intersection problems on coarse grained multicomputers, Proc. 11th Sympos. Theoret. Aspects Comput. Sci Dev91] Devroye (L.). 2811286. DF93] Devillers (O.) et Fabri (A.) Proc. 3rd Workshop Algorithms Data Struct, p.2777288, 1991.
, Grrnbaum (Branko) et Klee (Victor) Helly's Theorem and its Relatives, Proceedings of the symposium on pure mathematics, 1963.
, Docking two sets of spheres A survey of parallel computational geometry algorithms, Proc. International Workshop on Parallel Processing by Cellular Automata and Arrays, p.73388, 1988.
, Convex hulls of points from spherically symmetric distributions. In : Abstracts 1st Canad, Conf. Comput. Geom, issue.2
, Las Vegas gift-wrapping is twice as fast, Proc. 2nd Canad. Conf. Comput. Geom, p.2611264
, Two-variable linear programs are solvable in linear time, Math. Statist., Teesside Polytech, 1982.
, Linear time algorithms for two-and threevariable linear programs EC91] Emiris (I.) et Canny (J.). A general approach to removing degeneracies An eecient approach to removing geometric degeneracies, Proc. 32nd Annu. IEEE Sympos. Found. Comput . Sci., pp. 4055413. EC92] Emiris (I.) et Canny (J.) Proc. 8th Annu. ACM Sympos, pp.31145-74482, 1984.
, Algorithms in Combinatorial Geometry Geometric structures in computational geometry, Proc. 15th Internat. Colloq. Automata Lang. Program, p.2011213, 1987.
, The convex hull of a random set of points, Biometrika, vol.52, issue.3, p.3311343, 1965.
, The upper envelope of piecewise linear functions: algorithms and applications Parallel solutions to some geometric problems on the scan model of computation Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms, Guibas (L.) et Sharir Proceedings of the 1988 International Conference on Parallel Processing 2188222. EM88] Edelsbrunner (H.) et MMcke Proc. 4th Annu. ACM Sympos, p.3111336, 1989.
, An optimal algorithm for the ( k)-levels, with applications to separation and transversal problems, Proc. 9th Annu. ACM Sympos ES74] Erdos (P.) et Spencer (J.). Probabilistic Methods in Combinatorics, pp.38846-91, 1974.
, An $O(n\log ^2 h)$ Time Algorithm for the Three-Dimensional Convex Hull Problem, 2599277. ES92] Edelsbrunner (H.) et Shah (N. R.). Incremental topological ipping works for regular triangulations Proc. 8th Annu, 1991.
DOI : 10.1137/0220016
, Constructing belts in twodimensional arrangements with applications, Elements. Dover SIAM J. Comput, vol.15, p.2711284, 1956.
, A Threshold of log n for Approximating Set Cover
, Optimal packing and covering in the plane are NP-complete A new approach to the dynamic maintenance of maximal points in a plane Experimental evidence for the power of random sampling in practical parallel algorithms, 3655374. GG93] Ghouse (Mujtaba) et Goodrich 5499556. IEEE Computer Society. GJ79] Garey (M. R.) et Johnson (D. S.). Computers and Intractability: A Guide to the Theory of NP-Completeness, p.1333137, 1979.
, Probabilistic analysis of geometric algorithms Algorithms on sets and related problems, Dept. Comput. Sci., Princeton Univ. Comput. Sci, 1975.
, EEcient parallel techniques for computational geometry, West Lafayette Dept. Comput. Sci, 1987.
, Shelling pseudopolyhedra, Discrete Comput. Geom, vol.7, p.2077215, 1992.
, Convex Polytopes Analysis of a simple yet eecient convex hull algorithm Faster output-sensitive parallel convex hulls for d 3: optimal sublogarithmic algorithms for small outputs, Proc. 4th Annu. ACM Sympos Proc. 12th ACM Symp. on Computational Geometry, p.1533163, 1967.
, An optimal contour algorithm for iso-oriented rectangles, J. Algorithms, vol.5, p.3033326, 1984.
, Combinatorial Geometry in the Plane, Debrunner (H.) et Klee, 1964.
, Finding the upper envelope of n line segments in O(n log n) time Approximation schemes for covering and packing problems in image processing and VLSI, 1699174. HM84] Hochbaum (D. S.) et Maass, 1989.
, Spheres, molecules, and hidden surface removal, HO94] Halperin (D.) et Overmars Proc. 10th Annu. ACM Sympos, pp.1300136-1133122, 1984.
, Approximation Algorithms of the Set Covering and Vertex Cover Problems Three-clustering of points in the plane, HR93] Hagauer (J.) et Rote Proc. 1st European Symp. on Algorithms, pp.555-556, 1982.
, A pedestrian approach to ray shooting: Shoot a ray, take a walk Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane, Proc. 4th ACM-SIAM Sympos. Discrete Algorithms, pp. 54463. IA83] Imai (H.) et Asano, p.3100323, 1983.
, Dynamic maintenance of maximas of 2-d point sets, Proc. 10th Annu. ACM Sympos, p.1400149
, Reducibility among combinatorial problems GGommtrie Stochastique et Informatique Optimal search in planar subdivisions, Complexity of Computer Computations, 1972.
, Combinatorial Aspects of DavenporttSchinzel Sequences, 1995.
, On nding the maxima of a set of vectors, Luccio (F.) et Preparata, p.4699476, 1975.
, On Piercing Convex Sets, 1996.
, Fundamental Algorithms, The Art of Computer Programming, vol.1, 1973.
, Sorting and Searching The Art of Computer Programming, 1973.
, Seminumerical Algorithms The Art of Computer Programming, 1981.
, A Platform for Combinatorial Computing A framework for computational morphology In : Computational Geometry, d. par Toussaint (G. T.), pp. 2177248 The ultimate planar convex hull algorithm? Output-size sensitive algorithms for nding maximal vectors The ultimate planar convex hull algorithm?, Proc. 20th Allerton Conf. Commun. Control Comput., pp. 35542. Monticello, Illinois Proc. 1st Annu. ACM Sympos, pp.89996-2877299, 1982.
, Approximations and optimal geometric divideand-conquer, Proc. 23rd Annu. ACM Sympos. Theory Comput ., pp. 5055511. Also to appear in J. Comput. Syst. Sci
, EEcient partition trees, Proc. 7th Annu. ACM Sympos, p.119
, Linear optimization queries, J. Algorithms, vol.14, p.4322448, 1993.
, Delaunay triangulation and the convex hull of n points in expected linear time, BIT, vol.24, p.1511163, 1984.
, EEcient algorithms for enumerating intersecting intervals and rectangles, 1980.
, Optimistic Sorting and Information Theoretic Complexity, Proc. 4th ACM-SIAM Symp. on Disc. Alg, p.4677474
, The maximal number of faces of a convex polytope, Mathematica, vol.17, p.1799184, 1970.
, Linear-time algorithms for linear programming in R 3 and related problems, Proc. 23rd Annu. IEEE Sympos . Found. Comput. Sci, p.3299338
, Applying parallel computation algorithms in the design of serial algorithms, J. ACM, vol.30, pp.8522-865, 1983.
, Linear-time algorithms for linear programming in R 3 and related problems, SIAM J. Comput, vol.12, p.7599776, 1983.
, Linear programming in linear time when the dimension is xed, J. ACM, vol.31, p.1144127, 1984.
, Partitioning with two lines in the plane, J. Algorithms, vol.6, p.4300433, 1985.
, Multi-dimensional Searching and Computational Geometry, Data Structures and Algorithms, vol.3, 1984.
, Sorting and Searching, Data Structures and Algorithms, vol.1, 1984.
, Imai (Hiroshi) et Imai (Keiko) Enumeration of regular triangulations, Proc. 12th Annu. ACM Sympos, p.2244233
, Computational Geometry: An Introduction Through Randomized Algorithms Un Algorithme Optimal Sensible la Sortie pour le Calcul de l'Intersection de Demi-Espaces et d'un Convexe en Dimension 2, 1994.
, Output-sensitive Planar Convex Hull Algorithms on Coarse Grained Multicomputers, pp.93-06902
, Fast Stabbing of Boxes in High Dimensions, Research Report, 1996.
, Fast stabbing of boxes in high dimensions, Proc. 12th European Workshop on Comput. Geom.(CG96), p.121
, Fast stabbing of boxes in high dimensions, Proc. 8th Canad. Conf. Comput. Geom
, Output-sensitive Peeling of Convex and Maximal Layers An Output-Sensitive Convex Hull Algorithm for Planar Objects An Output-Sensitive Convex Hull Algorithm for Planar Objects, to appear. NY95] Nielsen (F.) et Yvinec NY96] Nielsen (F.) et Yvinec, 1995.
, Dynamically maintaining conngurations in the plane, Proc. 12th Annu. ACM Sympos. Theory Comput, p.1355145
, Maintenance of conngurations in the plane Convex hulls of nite sets of points in two and three dimensions Combinatorial Optimization: Algorithms and Complexity, PS85] Preparata (F. P.) et Shamos (M. I.). Computational Geometry: An Introduction, p.1666204, 1977.
, A convex hull algorithm for discs, and applications, Comput. Geom. Theory Appl, vol.1, issue.3, p.1711181, 1992.
, Algorithms in C++ Constructing higher-dimensional convex hulls at logarithmic cost per face, Sed92] Sedgewick (R.) Proc. 18th Annu. ACM Sympos. Theory Comput, p.4044413, 1983.
, Output-size sensitive algorithms for constructive problems in computational geometry, Dept. Comput. Sci, 1986.
, Almost linear upper bounds for the length of general Davenport-Schinzel sequences, Combinatorica, vol.7, p.1311143, 1987.
, Improved lower bounds on the length of Davenport-Schinzel sequences, Combinatorica, vol.8, p.1177124, 1988.
, A near-linear algorithm for the planar 2-center problem, Proc. 12th Annu. ACM Sympos, p.1066112
, A Tight Analysis of the Greedy Algorithm for Set Cover Vertical decomposition of a single cell in a three-dimensional arrangement of surfaces and its applications Convex hulls of piecewisesmooth Jordan curves). Finding the convex hull of a simple polygon in linear time A combinatorial bound for linear programming and related problems, Proc. of the 28-th ACM Symposium on Theory of Computing. SS96] Schwarzkopf (Otfried) et Sharir (Micha) Proc. 12th Annu. ACM Sympos SW92] Sharir (M.) et Welzl (E.) Proc. 9th Sympos. Theoret. Aspects Comput. Sci, pp.66694-4533458, 1986.
, -center problems, Proceedings of the twelfth annual symposium on Computational geometry , SCG '96, p.1222132
DOI : 10.1145/237218.237255
URL : https://hal.archives-ouvertes.fr/inria-00074481
, Finding the convex hull facet by facet, J. Algorithms, vol.6, p.17748, 1985.
, Data Structures and Network Algorithms Covering image subsets with patches, Proc. of the 5-th international conference on pattern recognition, p.8355839, 1987.
, Parallel Computational Geometry Using Polygonal Order, 1985.
, Eigenschaften der Nerven homologish-einfacher Familien im R n, Thhse de PhD, 1967.
, Planar realizations of nonlinear Davenport-Schinzel sequences by segments, Discrete Comput. Geom, vol.3, p.15547, 1988.
, On nding the maximal elements in a set of plane vectors, Comput. Sci, 1974.
, Symbolic treatment of geometric degeneracies
, Lectures on Polytopes, Graduate Texts in Mathematics, vol.152, 1994.