Incremental constructions con BRIO

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Incremental constructions con BRIO

Full text

Pdf (485 KB)

Source

Annual Symposium on Computational Geometry archive
Proceedings of the nineteenth annual symposium on Computational geometry table of contents

San Diego, California, USA

SESSION: Models and meshes table of contents

Pages: 211 - 219

Year of Publication: 2003

ISBN:1-58113-663-3

Authors

Nina Amenta	University of California at Davis
Sunghee Choi	University of Texas at Austin
Günter Rote	Freie Universitat Berlin

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques
ACM: Association for Computing Machinery

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 22, Citation Count: 9

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/777792.777824 What is a DOI?

ABSTRACT

Randomized incremental constructions are widely used in computational geometry, but they perform very badly on large data because of their inherently random memory access patterns. We define a biased randomized insertion order which removes enough randomness to significantly improve performance, but leaves enough randomness so that the algorithms remain theoretically optimal.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Pankaj K. Agarwal , Mark de Berg , Jirí Matousek , Otfried Schwarzkopf, Constructing Levels in Arrangements and Higher Order Voronoi Diagrams, SIAM Journal on Computing, v.27 n.3, p.654-667, June 1998 [doi>10.1137/S0097539795281840]
	2	Lars Arge, External memory data structures, Handbook of massive data sets, Kluwer Academic Publishers, Norwell, MA, 2002
	3	Tetsuo Asano , Desh Ranjan , Thomas Roos , Emo Welzl , Peter Widmayer, Space-filling curves and their use in the design of geometric data structures, Theoretical Computer Science, v.181 n.1, p.3-15, July 15, 1997 [doi>10.1016/S0304-3975(96)00259-9]
	4	C. Bradford Barber , David P. Dobkin , Hannu Huhdanpaa, The quickhull algorithm for convex hulls, ACM Transactions on Mathematical Software (TOMS), v.22 n.4, p.469-483, Dec. 1996 [doi>10.1145/235815.235821]
	5	Bartholdi, III, J. J., and Platzman, L. K. A fast heuristic based on spacefilling curves for minimum-weight matching in the plane. Inform. Process. Lett. 17 (1983), 177--180.
	6	Blelloch, G. E., Miller, G. L., Hardwick, J. C., and Talmor, D. Design and implementation of a practical parallel Delaunay algorithm. Algorithmica 24, 3 (1999), 243--269.
	7	Chan, T. M., Snoeyink, J., and Yap, C. K. Primal dividing and dual pruning: Output-sensitive construction of 4-d polytopes and 3-d Voronoi diagrams. Discrete Comput. Geom. 18 (1997), 433--454.
	8	L. P Chew, Building Voronoi Diagrams for Convex Polygons in Linear Expected Time, Dartmouth College, Hanover, NH, 1990
	9	Sunghee Choi , Nina Amenta, Delaunay triangulation programs on surface data, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.135-136, January 06-08, 2002, San Francisco, California
	10	Cignoni, P., Montani, C. and Scopigno, R. DeWall: a fast divide and conquer Delaunay triangulation algorithm in Ed. Computer-Aided Design 30, 5 (1998), 333--341.
	11	Clarkson, K. L. New applications of random sampling in computational geometry. Discrete Comput. Geom. 2 (1987), 195--222.
	12	Kenneth L. Clarkson , Kurt Mehlhorn , Raimund Seidel, Four results on randomized incremental constructions, Computational Geometry: Theory and Applications, v.3 n.4, p.185-212, Sept. 1993 [doi>10.1016/0925-7721(93)90009-U]
	13	K. L. Clarkson , P. W. Shor, Applications of random sampling in computational geometry, II, Discrete & Computational Geometry, v.4 n.5, p.387-421, 1989 [doi>10.1007/BF02187740]
	14	Mark de Berg , Marc van Kreveld , Mark Overmars , Otfried Schwarzkopf, Computational geometry: algorithms and applications, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
	15	Devillers, O. The Delaunay hierarchy. Int. Journ. Found. of Comp. Sci., 13 (2002), 163--180.
	16	Devillers, O., and Guigue, P. The shuffling buffer. Internat. J. Comput. Geom. Appl. 11 (2001), 555--572.
	17	Rex Allen Dwyer, Average-case analysis of algorithms for convex hulls and Voronoi diagrams, Carnegie Mellon University, Pittsburgh, PA, 1988
	18	Rex A. Dwyer, Higher-dimensional Voronoi diagrams in linear expected time, Discrete & Computational Geometry, v.6 n.4, p.343-367, 1991 [doi>10.1007/BF02574694]
	19	Golin, M. J., and Na, H.-S. On the average complexity of 3d-Voronoi diagrams of random points on convex polytopes. In Proc. 12th Annu. ACM Sympos. Comput. Geom. (2000), pp. 127--135.
	20	Golin, M. J., and Na, H.-S. On the average complexity of 3d-Voronoi diagrams of random points on convex polytopes. Tech. Rep. Tech. report HKUST-TCSC-2001-08, Hong Kong University of Science and Technology, 2001. http://www.cs.ust.hk/tcsc/RR/2001-08.ps.gz.
	21	Golin, M. J., and Na, H.-S. On the proofs of two lemmas describing the intersections of spheres with the boundary of a convex polytope. Tech. Rep. Tech. report HKUST-TCSC-2001-09, Hong Kong University of Science and Technology, 2001. http://www.cs.ust.hk/tcsc/RR/2001-09.ps.gz.
	22	Goodrich, M. T., Tsay, J.-J., Vengroff, D. E., and Vitter J. S. External-Memory Computational Geometry, In Proc. 34th Foundations of Computer Science (FOCS) (1993), pp. 714--723.
	23	K. Mulmuley, A fast planar partition algorithm, I, Journal of Symbolic Computation, v.10 n.3-4, p.253-280, Sept./Oct. 1990 [doi>10.1016/S0747-7171(08)80064-8]
	24	Kentan Mulmuley, A fast planar partition algorithm, II, Journal of the ACM (JACM), v.38 n.1, p.74-103, Jan. 1991 [doi>10.1145/102782.102785]
	25	Ketan Mulmuley, On levels in arrangements and Voronoi diagrams, Discrete & Computational Geometry, v.6 n.4, p.307-338, 1991 [doi>10.1007/BF02574692]
	26	Mulmuley, K. Computational Geometry: An Introduction Through Randomized Algorithms. Prentice Hall, Englewood Cliffs, NJ, 1993.
	27	Ketan Mulmuley , Otfried Schwarzkopf, Randomized algorithms, Handbook of discrete and computational geometry, CRC Press, Inc., Boca Raton, FL, 1997
	28	Loren K. Platzman , John J. Bartholdi, III, Spacefilling curves and the planar travelling salesman problem, Journal of the ACM (JACM), v.36 n.4, p.719-737, Oct. 1989 [doi>10.1145/76359.76361]
	29	Sagan, H. Space-filling curves. Springer-Verlag, New York, 1994.
	30	Raimund Seidel, A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons, Computational Geometry: Theory and Applications, v.1 n.1, p.51-64, July 1991 [doi>10.1016/S0925-7721(99)00042-5]
	31	Raimund Seidel, Small-dimensional linear programming and convex hulls made easy, Discrete & Computational Geometry, v.6 n.5, p.423-434, 1991 [doi>10.1007/BF02574699]
	32	Seidel, R. Backwards analysis of randomized geometric algorithms. In New Trends in Discrete and Computational Geometry, J. Pach, Ed., vol. 10 of Algorithms and Combinatorics. Springer-Verlag, 1993, pp. 37--68.
	33	Welzl, E. Smallest enclosing disks (balls and ellipsoids). In New Results and New Trends in Computer Science, H. Maurer, Ed., vol. 555 of Lecture Notes Comput. Sci. Springer-Verlag, 1991, pp. 359--370.
	34	Binhai Zhu, Further Computational Geometry in Secondary Memory, Proceedings of the 5th International Symposium on Algorithms and Computation, p.514-522, August 25-27, 1994

CITED BY 9

	Leonidas Guibas , Daniel Russel, An empirical comparison of techniques for updating Delaunay triangulations, Proceedings of the twentieth annual symposium on Computational geometry, June 08-11, 2004, Brooklyn, New York, USA
	Sheng Zhou , Christopher B. Jones, HCPO: an efficient insertion order for incremental Delaunay triangulation, Information Processing Letters, v.93 n.1, p.37-42, 16 January 2005
	Martin Isenburg , Yuanxin (Leo) Liu , Jonathan Shewchuk , Jack Snoeyink, Illustrating the streaming construction of 2D delaunay triangulations, Proceedings of the twenty-second annual symposium on Computational geometry, June 05-07, 2006, Sedona, Arizona, USA
	Bernard Chazelle , Wolfgang Johann Heinrich Mulzer, Markov incremental constructions, Proceedings of the twenty-fourth annual symposium on Computational geometry, June 09-11, 2008, College Park, MD, USA
	Daniel K. Blandford , Guy E. Blelloch , Clemens Kadow, Engineering a compact parallel delaunay algorithm in 3D, Proceedings of the twenty-second annual symposium on Computational geometry, June 05-07, 2006, Sedona, Arizona, USA
	Martin Isenburg , Yuanxin Liu , Jonathan Shewchuk , Jack Snoeyink, Streaming computation of Delaunay triangulations, ACM Transactions on Graphics (TOG), v.25 n.3, July 2006
	Vicente H.F. Batista , David L. Millman , Sylvain Pion , Johannes Singler, Parallel geometric algorithms for multi-core computers, Proceedings of the 25th annual symposium on Computational geometry, June 08-10, 2009, Aarhus, Denmark
	Jean-Daniel Boissonnat , Olivier Devillers , Samuel Hornus, Incremental construction of the delaunay triangulation and the delaunay graph in medium dimension, Proceedings of the 25th annual symposium on Computational geometry, June 08-10, 2009, Aarhus, Denmark
	Timothy M. Chan , Eric Y. Chen, Optimal in-place algorithms for 3-D convex hulls and 2-D segment intersection, Proceedings of the 25th annual symposium on Computational geometry, June 08-10, 2009, Aarhus, Denmark