|
[AA95]
|
O. Aichholzer and F. Aurenhammer.
Straight skeletons for general polygonal figures.
Technical Report 432, Inst. for Theor. Comput. Sci., Graz Univ. of
Technology, Graz, Austria, 1995.
|
|
[AAAG95]
|
O. Aichholzer, D. Alberts, F. Aurenhammer, and B. Gärtner.
A novel type of skeleton for polygons.
J. Universal Comput. Sci., 1(12):752-761, 1995.
|
|
[AAD07]
|
Nina Amenta, Dominique Attali, and Olivier Devillers.
Complexity of Delaunay triangulation for points on
lower-dimensional polyhedra.
In Proc. 18th ACM-SIAM Sympos. Discrete Algorithms, pages
1106-1113, 2007.
|
|
[AB99]
|
Nina Amenta and Marshall Bern.
Surface reconstruction by Voronoi filtering.
Discrete Comput. Geom., 22(4):481-504, 1999.
|
|
[AB03]
|
Dominique Attali and Jean-Daniel Boissonnat.
Complexity of the Delaunay triangulation of points on polyhedral
surfaces.
Discrete and Computational Geometry, 30(3):437-452, 2003.
|
|
[Abb]
|
J. Abbott.
Quadratic interval refinement for real roots.
Poster presented at the 2006 Int. Symp. on Symb. and Alg. Comp. (ISSAC 2006).
|
|
[ABL03]
|
Dominique Attali, Jean-Daniel Boissonnat, and André Lieutier.
Complexity of the Delaunay triangulation of points on surfaces: The
smooth case.
In Proc. 19th Annual Symposium on Computational Geometry, pages
237-246, 2003.
|
|
[ACSYD05]
|
Pierre Alliez, David Cohen-Steiner, Mariette Yvinec, and Mathieu Desbrun.
Variational tetrahedral meshing.
ACM Transactions on Graphics, 24:617-625, 2005.
SIGGRAPH '2005 Conference Proceedings.
|
|
[AFH02]
|
P. K. Agarwal, E. Flato, and D. Halperin.
Polygon decomposition for efficient construction of Minkowski sums.
Computational Geometry: Theory and Applications, 21:39-61,
2002.
|
|
[AKM+87]
|
A. Aggarwal, M. M. Klawe, S. Moran, P. W. Shor, and R. Wilber.
Geometric applications of a matrix-searching algorithm.
Algorithmica, 2:195-208, 1987.
|
|
[Ale01]
|
Andrei Alexandrescu.
Modern C++ Design: Generic Programming and Design Patterns
Applied.
Addison-Wesley, 2001.
|
|
[AM93a]
|
S. Arya and D. M. Mount.
Algorithms for fast vector quantization.
In Data Compression Conference, pages 381-390. IEEE Press,
1993.
|
|
[AM93b]
|
S. Arya and D. M. Mount.
Approximate nearest neighbor queries in fixed dimensions.
In Proc. 4th ACM-SIAM Sympos. Discrete Algorithms, pages
271-280, 1993.
|
|
[And78]
|
K. R. Anderson.
A reevaluation of an efficient algorithm for determining the convex
hull of a finite planar set.
Inform. Process. Lett., 7(1):53-55, 1978.
|
|
[And79]
|
A. M. Andrew.
Another efficient algorithm for convex hulls in two dimensions.
Inform. Process. Lett., 9(5):216-219, 1979.
|
|
[AS00]
|
Pankaj K. Agarwal and Micha Sharir.
Arrangements and their applications.
In Jörg-Rüdiger Sack and Jorge Urrutia, editors, Handbook of Computational Geometry, pages 49-119. Elsevier Science
Publishers B.V. North-Holland, Amsterdam, 2000.
|
|
[AT78]
|
S. G. Akl and G. T. Toussaint.
A fast convex hull algorithm.
Inform. Process. Lett., 7(5):219-222, 1978.
|
|
[Aus98]
|
Matthew H. Austern.
Generic Programming and the STL.
Addison-Wesley, 1998.
|
|
[Bau75]
|
B. G. Baumgart.
A polyhedron representation for computer vision.
In Proc. AFIPS Natl. Comput. Conf., volume 44, pages 589-596.
AFIPS Press, Alrington, Va., 1975.
|
|
[BB97]
|
F. Bernardini and C. Bajaj.
Sampling and reconstructing manifolds using alpha-shapes.
Technical Report CSD-TR-97-013, Dept. Comput. Sci., Purdue Univ.,
West Lafayette, IN, 1997.
|
|
[BBP01]
|
H. Brönnimann, C. Burnikel, and S. Pion.
Interval arithmetic yields efficient dynamic filters for
computational geometry.
Discrete Applied Mathematics, 109:25-47, 2001.
|
|
[BDH96]
|
C. Bradford Barber, David P. Dobkin, and Hannu Huhdanpaa.
The Quickhull algorithm for convex hulls.
ACM Trans. Math. Softw., 22(4):469-483, December 1996.
|
|
[BDP+02]
|
Jean-Daniel Boissonnat, Olivier Devillers, Sylvain Pion, Monique Teillaud, and
Mariette Yvinec.
Triangulations in CGAL.
Comput. Geom. Theory Appl., 22:5-19, 2002.
|
|
[BDTY00]
|
Jean-Daniel Boissonnat, Olivier Devillers, Monique Teillaud, and Mariette
Yvinec.
Triangulations in CGAL.
In Proc. 16th Annu. ACM Sympos. Comput. Geom., pages 11-18,
2000.
|
|
[BEH+02]
|
Eric Berberich, Arno Eigenwillig, Michael Hemmer, Susan Hert, Kurt Mehlhorn,
and Elmar Schömer.
A computational basis for conic arcs and boolean operations on conic
polygons.
In Rolf Möhring and Rajeev Raman, editors, Algorithms - ESA
2002: 10th Annual European Symposium, volume 2461 of Lecture Notes in
Computer Science, pages 174-186, Rome, Italy, September 2002. Springer.
|
|
[BEH+05]
|
Eric Berberich, Arno Eigenwillig, Michael Hemmer, Susan Hert, Lutz Kettner,
Kurt Mehlhorn, Joachim Reichel, Susanne Schmitt, Elmar Schömer, and
Nicola Wolpert.
Exacus: Efficient and exact algorithms for curves and surfaces.
In Gerth S. Brodal and Stefano Leonardi, editors, 13th Annual
European Symposium on Algorithms (ESA 2005), volume 3669 of Lecture
Notes in Computer Science, pages 155-166, Palma de Mallorca, Spain, October
2005. European Association for Theoretical Computer Science (EATCS),
Springer.
|
|
[Ben75]
|
J. L. Bentley.
Multidimensional binary search trees used for associative searching.
Commun. ACM, 18(9):509-517, September 1975.
|
|
[BEPP99]
|
Hervé Brönnimann, Ioannis Emiris, Victor Pan, and Sylvain Pion.
Sign determination in Residue Number Systems.
Theoret. Comput. Sci., 210(1):173-197, 1999.
Special Issue on Real Numbers and Computers.
|
|
[BF02]
|
Jean-Daniel Boissonnat and Julia Flötotto.
A local coordinate system on a surface.
In Proc. 7th ACM Symposium on Solid Modeling and Applications,
2002.
|
|
[BFH95]
|
Heinzgerd Bendels, Dieter W. Fellner, and Sven Havemann.
Modellierung der grundlagen: Erweiterbare datenstrukturen zur
modellierung und visualisierung polygonaler welten.
In D. W. Fellner, editor, Modeling - Virtual Worlds -
Distributed Graphics, pages 149-157, Bad Honnef / Bonn, 27.-28. November
1995.
|
|
[BGH97]
|
Julien Basch, Leonidas Guibas, and John Hershberger.
Data structures for mobile data.
In Proceedings of the 8th Annual ACM-SIAM Symposium on
Discrete Algorithms, pages 747-756, 1997.
|
|
[BHKT07]
|
Eric Berberich, Michael Hemmer, Menelaos I. Karavelas, and Monique Teillaud.
Revision of the interface specification of algebraic kernel.
Technical Report ACS-TR-243301-01, INRIA Sophia-Antipolis, Max Planck
Institut für Informatik, National University of Athens, 2007.
|
|
[BMS94]
|
C. Burnikel, K. Mehlhorn, and S. Schirra.
On degeneracy in geometric computations.
In Proc. 5th ACM-SIAM Sympos. Discrete Algorithms, pages
16-23, 1994.
|
|
[BO05]
|
Jean-Daniel Boissonnat and Steve Oudot.
Provably good sampling and meshing of surfaces.
Graphical Models, 67:405-451, 2005.
|
|
[BPP95]
|
Gavin Bell, Anthony Parisi, and Mark Pesce.
Vrml the virtual reality modeling language: Version 1.0
specification.
http://www.vrml.org/, May 26 1995.
Third Draft.
|
|
[Bro97]
|
J. L. Brown.
Systems of coordinates associated with points scattered in the plane.
Comput. Aided Design, 14:547-559, 1997.
|
|
[Bur96]
|
C. Burnikel.
Exact Computation of Voronoi Diagrams and Line Segment
Intersections.
Ph.D thesis, Universität des Saarlandes, March 1996.
|
|
[BY98]
|
Jean-Daniel Boissonnat and Mariette Yvinec.
Algorithmic Geometry.
Cambridge University Press, UK, 1998.
Translated by Hervé Brönnimann.
|
|
[Byk78]
|
A. Bykat.
Convex hull of a finite set of points in two dimensions.
Inform. Process. Lett., 7:296-298, 1978.
|
|
[C++98]
|
International standard ISO/IEC 14882: Programming languages - C++.
American National Standards Institute, 11 West 42nd Street, New York
10036, 1998.
|
|
[CC78]
|
E. Catmull and J. Clark.
Recursively generated B-spline surfaces on arbitrary topological
meshes.
Computer Aided Design, 10:350-355, 1978.
|
|
[CD85]
|
Bernard Chazelle and D. P. Dobkin.
Optimal convex decompositions.
In G. T. Toussaint, editor, Computational Geometry, pages
63-133. North-Holland, Amsterdam, Netherlands, 1985.
|
|
[CDE+00]
|
Siu-Wing Cheng, Tamal K. Dey, Herbert Edelsbrunner, Michael A. Facello, and
Shang-Hua Teng.
Sliver exudation.
J. ACM, 47(5):883-904, 2000.
|
|
[Cha84]
|
Bernard Chazelle.
Convex partitions of polyhedra: a lower bound and worst-case optimal
algorithm.
SIAM J. Comput., 13:488-507, 1984.
|
|
[Che04]
|
L. Chen.
Mesh Smoothing Schemes based on Optimal Delaunay Triangulations.
In Proceedings of 13th International Meshing Roundtable, pages
109-120, 2004.
|
|
[Che09]
|
Otfried Cheong.
IPE manual and library documentation, 6.0pre32 edition, 2009.
|
|
[CLRS01]
|
T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein.
Introduction to Algorithms.
MIT Press, Cambridge, MA, 2nd edition, 2001.
|
|
[CMS93]
|
K. L. Clarkson, K. Mehlhorn, and R. Seidel.
Four results on randomized incremental constructions.
Comput. Geom. Theory Appl., 3(4):185-212, 1993.
|
|
[CP05a]
|
F. Cazals and M. Pouget.
Estimating differential quantities using polynomial fitting of
osculating jets.
Computer Aided Geometric Design, 22(2), 2005.
Conference version: Symp. on Geometry Processing 2003.
|
|
[CP05b]
|
F. Cazals and M. Pouget.
Smooth surfaces, umbilics, lines of curvatures, foliations, ridges
and the medial axis: selected topics.
Int. J. of Computational Geometry and Applications,
15(5):511-536, 2005.
|
|
[CP05c]
|
F. Cazals and M. Pouget.
Topology driven algorithms for ridge extraction on meshes.
Technical Report RR-5526, INRIA, 2005.
|
|
[CT09]
|
Manuel Caroli and Monique Teillaud.
Computing 3D periodic triangulations.
In Proceedings 17th European Symposium on Algorithms, volume
5757 of Lecture Notes in Computer Science, pages 37-48, 2009.
Full version available as INRIA Research Report 6823
http://hal.inria.fr/inria-00356871.
|
|
[dBvKOS97]
|
Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf.
Computational Geometry: Algorithms and Applications.
Springer-Verlag, Berlin, 1997.
|
|
[dBvKOS00]
|
Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf.
Computational Geometry: Algorithms and Applications.
Springer-Verlag, Berlin, Germany, 2nd edition, 2000.
|
|
[dC76]
|
M. de Carmo.
Differential Geometry of Curves and Surfaces.
Prentice Hall, Englewood Cliffs, NJ, 1976.
|
|
[dCCLT09]
|
Pedro M.M. de Castro, Frederic Cazals, Sebastien Loriot, and Monique Teillaud.
Design of the CGAL 3D Spherical Kernel and application to
arrangements of circles on a sphere.
Computational Geometry : Theory and Applications, 42(6-7):536
- 550, 2009.
|
|
[DEGN99]
|
Tamal Dey, Herbert Edelsbrunner, Sumanta Guha, and Dmitry Nekhayev.
Topology preserving edge contraction. geometric combinatorics.
Publ. Inst. Math. (Beograd) (N.S.), 66:23-45, 1999.
|
|
[Dev98]
|
Olivier Devillers.
Improved incremental randomized Delaunay triangulation.
In Proc. 14th Annu. ACM Sympos. Comput. Geom., pages 106-115,
1998.
|
|
[Dev02]
|
Olivier Devillers.
The Delaunay hierarchy.
Internat. J. Found. Comput. Sci., 13:163-180, 2002.
|
|
[Dev09]
|
Olivier Devillers.
Vertex removal in two dimensional Delaunay triangulation:
Asymptotic complexity is pointless.
Research Report 7104, INRIA, 2009.
|
|
[DFG99]
|
Q. Du, V. Faber, and M. Gunzburger.
Centroidal Voronoi Tessellations: Applications and Algorithms.
SIAM review, 41(4):637-676, 1999.
|
|
[DFMT00]
|
Olivier Devillers, Alexandra Fronville, Bernard Mourrain, and Monique Teillaud.
Algebraic methods and arithmetic filtering for exact predicates on
circle arcs.
In Proc. 16th Annu. ACM Sympos. Comput. Geom., pages 139-147,
2000.
|
|
[DFMT02]
|
Olivier Devillers, Alexandra Fronville, Bernard Mourrain, and Monique Teillaud.
Algebraic methods and arithmetic filtering for exact predicates on
circle arcs.
Comput. Geom. Theory Appl., 22:119-142, 2002.
|
|
[DLPT98]
|
Olivier Devillers, Giuseppe Liotta, Franco P. Preparata, and Roberto Tamassia.
Checking the convexity of polytopes and the planarity of
subdivisions.
Comput. Geom. Theory Appl., 11:187-208, 1998.
|
|
[DMA02]
|
Mathieu Desbrun, Mark Meyer, and Pierre Alliez.
Intrinsic parameterizations of surface meshes.
Computer Graphics Forum, 21(3):209-218, September
2002.
|
|
[DP03]
|
Olivier Devillers and Sylvain Pion.
Efficient exact geometric predicates for Delaunay triangulations.
In Proc. 5th Workshop Algorithm Eng. Exper., pages 37-44,
2003.
|
|
[DPT02]
|
Olivier Devillers, Sylvain Pion, and Monique Teillaud.
Walking in a triangulation.
Internat. J. Found. Comput. Sci., 13:181-199, 2002.
|
|
[DT03]
|
Olivier Devillers and Monique Teillaud.
Perturbations and vertex removal in a 3D Delaunay triangulation.
In Proc. 14th ACM-SIAM Sympos. Discrete Algorithms (SODA),
pages 313-319, 2003.
|
|
[DT06]
|
Olivier Devillers and Monique Teillaud.
Perturbations and vertex removal in Delaunay and regular 3D
triangulations.
Research Report 5968, INRIA, 2006.
http://hal.inria.fr/inria-00090522.
|
|
[DW02]
|
Q. Du and D. Wang.
Tetrahedral mesh generation and optimization based on centroidal
Voronoi tessellations.
International Journal for Numerical Methods in Engineering,
56:1355-1373, 2002.
|
|
[Dwy89]
|
R. A. Dwyer.
Higher-dimensional Voronoi diagrams in linear expected time.
In Proc. 5th Annu. ACM Sympos. Comput. Geom., pages 326-333,
1989.
|
|
[Edd77]
|
W. F. Eddy.
A new convex hull algorithm for planar sets.
ACM Trans. Math. Softw., 3:398-403 and 411-412, 1977.
|
|
[EDD+95]
|
Matthias Eck, Tony DeRose, Tom Duchamp, Hugues Hoppe, Michael Lounsbery, and
Werner Stuetzle.
Multiresolution analysis of arbitrary meshes.
In Computer Graphics (Proc. SIGGRAPH '95), volume 29, pages
173-182, 1995.
Examples in ftp://ftp.cs.washington.edu/pub/graphics.
|
|
[Ede92]
|
H. Edelsbrunner.
Weighted alpha shapes.
Technical Report UIUCDCS-R-92-1760, Dept. Comput. Sci., Univ.
Illinois, Urbana, IL, 1992.
|
|
[Ede99]
|
H. Edelsbrunner.
Deformable smooth surface design.
Discrete Comput. Geom., 21:87-115, 1999.
|
|
[EE98]
|
David Eppstein and Jeff Erickson.
Raising roofs, crashing cycles, and playing pool: Applications of a
data structure for finding pairwise interactions.
In Symposium on Computational Geometry, pages 58-67, 1998.
|
|
[Eig08]
|
Arno Eigenwillig.
Real Root Isolation for Exactand Approximate Polynomials Using
Descartes ' Rule of Signs.
PhD thesis, Universität des Saarlandes, Saarbrücken, Germany,
2008.
|
|
[EK99]
|
G. Elber and M.-S. Kim, editors.
Computer Aided Design, volume 31, 1999.
Special Issue on Offsets, Sweeps and Minkowski Sums.
|
|
[EK08]
|
Arno Eigenwillig and Michael Kerber.
Exact and efficient 2d-arrangements of arbitrary algebraic curves.
In Proceedings of the Nineteenth Annual ACM-SIAM Symposium on
Discrete Algorithms (SODA08), 2008.
122-131.
|
|
[EKP+04]
|
Ioannis Z. Emiris, Athanasios Kakargias, Sylvain Pion, Monique Teillaud, and
Elias P. Tsigaridas.
Towards an open curved kernel.
In Proc. 20th Annu. ACM Sympos. Comput. Geom., pages 438-446,
2004.
|
|
[EKW07]
|
Arno Eigenwillig, Michael Kerber, and Nicola Wolpert.
Fast and exact geometric analysis of real algebraic plane curves.
In Christopher W. Brown, editor, Proocedings of the 2007
International Symposium on Symbolic and Algebraic Computation (ISSAC 2007),
pages 151-158, 2007.
|
|
[EM94]
|
H. Edelsbrunner and E. P. Mücke.
Three-dimensional alpha shapes.
ACM Trans. Graph., 13(1):43-72, January 1994.
|
|
[Eri02]
|
Jeff Erickson.
Dense point sets have sparse Delaunay triangulations.
In Proc. 13th ACM-SIAM Sympos. Discrete Algorithms (SODA),
pages 125-134, 2002.
|
|
[ES96]
|
H. Edelsbrunner and N. R. Shah.
Incremental topological flipping works for regular triangulations.
Algorithmica, 15:223-241, 1996.
|
|
[Far90]
|
G. Farin.
Surfaces over Dirichlet tesselations.
Comput. Aided Geom. Design, 7:281-292, 1990.
|
|
[FBF77]
|
J. H. Friedman, J. L. Bentley, and R. A. Finkel.
An algorithm for finding best matches in logarithmic expected time.
ACM Trans. Math. Softw., 3:209-226, 1977.
|
|
[FH00]
|
Eyal Flato and Dan Halperin.
Robust and efficient construction of planar Minkowski sums.
In Abstracts 16th European Workshop Comput. Geom., pages
85-88. Ben-Gurion University of the Negev, 2000.
|
|
[FH05]
|
M. S. Floater and K. Hormann.
Surface parameterization: a tutorial and survey.
In N. A. Dodgson, M. S. Floater, and M. A. Sabin, editors, Advances in Multiresolution for Geometric Modelling, Mathematics and
Visualization, pages 157-186. Springer, Berlin, Heidelberg, 2005.
|
|
[FJ83]
|
G. N. Frederickson and D. B. Johnson.
Finding kth paths and p-centers by generating and searching good
data structures.
J. Algorithms, 4:61-80, 1983.
|
|
[FJ84]
|
G. N. Frederickson and D. B. Johnson.
Generalized selection and ranking: sorted matrices.
SIAM J. Comput., 13:14-30, 1984.
|
|
[Flo03a]
|
Michael Floater.
Mean value coordinates.
Computer Aided Design, 20(1):19-27, 2003.
|
|
[Flö03b]
|
Julia Flötotto.
A coordinate system associated to a point cloud issued from a
manifold: definition, properties and applications.
Thèse de doctorat en sciences, Université de Nice-Sophia
Antipolis, France, 2003.
|
|
[FO98]
|
Petr Felkel and Stěpán Obdržálek.
Straight skeleton implementation.
In László Szirmay Kalos, editor, 14th Spring
Conference on Computer Graphics (SCCG'98), pages 210-218, 1998.
|
|
[Gär99]
|
B. Gärtner.
Fast and robust smallest enclosing balls.
In Proc. 7th annu. European Symposium on Algorithms (ESA),
volume 1643 of Lecture Notes in Computer Science, pages 325-338.
Springer-Verlag, 1999.
|
|
[GGHT97]
|
M. Goodrich, L. J. Guibas, J. Hershberger, and P. Tanenbaum.
Snap rounding line segments efficiently in two and three dimensions.
In Proc. 13th Annu. ACM Sympos. Comput. Geom., pages 284-293,
1997.
|
|
[GH97]
|
M. Garland and P. S. Heckbert.
Surface simplification using quadric error metrics.
In Proc. SIGGRAPH '97, pages 209-216, 1997.
|
|
[GHH+03]
|
Miguel Granados, Peter Hachenberger, Susan Hert, Lutz Ketter, Kurt Mehlhorn,
and Michael Seel.
Boolean operations on 3d selective nef complexes data structure,
algorithms, and implementation.
In Giuseppe Di Battista and Uri Zwick, editors, Algorithms - ESA
2003: 11th Annual European Symposium, volume 2832 of Lecture Notes in
Computer Science, pages 174-186, Budapest, Hugary, September 2003.
Springer.
|
|
[GHJV95]
|
E. Gamma, R. Helm, R. Johnson, and J. Vlissides.
Design Patterns - Elements of Reusable Object-Oriented
Software.
Addison-Wesley, 1995.
|
|
[GKR04]
|
Leonidas Guibas, Menelaos Karaveles, and Daniel Russel.
A computational framework for handling motion.
In Proceedings of the Sixth Workshop on Algorithm Engineering
and Experiments, pages 129-141, 2004.
|
|
[GM98]
|
Leonidas Guibas and David Marimont.
Rounding arrangements dynamically.
Internat. J. Comput. Geom. Appl., 8:157-176, 1998.
|
|
[Gra]
|
Torbjörn Granlund.
GMP, the GNU multiple precision arithmetic library.
http://gmplib.org/.
|
|
[Gra72]
|
R. L. Graham.
An efficient algorithm for determining the convex hull of a finite
planar set.
Inform. Process. Lett., 1:132-133, 1972.
|
|
[Gre83]
|
Daniel H. Greene.
The decomposition of polygons into convex parts.
In Franco P. Preparata, editor, Computational Geometry,
volume 1 of Adv. Comput. Res., pages 235-259. JAI Press, Greenwich,
Conn., 1983.
|
|
[GRS83]
|
Leonidas J. Guibas, L. Ramshaw, and J. Stolfi.
A kinetic framework for computational geometry.
In Proc. 24th Annu. IEEE Sympos. Found. Comput. Sci., pages
100-111, 1983.
|
|
[GS78]
|
Leonidas J. Guibas and R. Sedgewick.
A dichromatic framework for balanced trees.
In Proc. 19th Annu. IEEE Sympos. Found. Comput. Sci., Lecture
Notes Comput. Sci., pages 8-21. Springer-Verlag, 1978.
|
|
[GS85]
|
Leonidas J. Guibas and J. Stolfi.
Primitives for the manipulation of general subdivisions and the
computation of Voronoi diagrams.
ACM Trans. Graph., 4(2):74-123, April 1985.
|
|
[GS97a]
|
B. Gärtner and S. Schönherr.
Exact primitives for smallest enclosing ellipses.
In Proc. 13th Annu. ACM Sympos. Comput. Geom., pages 430-432,
1997.
|
|
[GS97b]
|
Bernd Gärtner and Sven Schönherr.
Smallest enclosing ellipses - fast and exact.
Serie B - Informatik B 97-03, Freie Universität Berlin, Germany,
June 1997.
URL
http://www.inf.fu-berlin.de/inst/pubs/tr-b-97-03.abstract.html.
|
|
[GS98a]
|
Bernd Gärtner and Sven Schönherr.
Smallest enclosing circles - an exact and generic implementation in
C++.
Serie B - Informatik B 98-04, Freie Universität Berlin, Germany,
April 1998.
URL
http://www.inf.fu-berlin.de/inst/pubs/tr-b-98-04.abstract.html.
|
|
[GS98b]
|
Bernd Gärtner and Sven Schönherr.
Smallest enclosing ellipses - an exact and generic implementation in
C++.
Serie B - Informatik B 98-05, Freie Universität Berlin, Germany,
April 1998.
URL
http://www.inf.fu-berlin.de/inst/pubs/tr-b-98-05.abstract.html.
|
|
[GS00]
|
Bernd Gärtner and Svend Schönherr.
An efficient, exact, and generic quadratic programming solver for
geometric optimization.
In Proc. 16th Annu. ACM Sympos. Comput. Geom., pages 110-118,
2000.
|
|
[GvL83]
|
G. Golub and C. van Loan.
Matrix Computations.
Johns Hopkins Univ. Press, Baltimore, MA, 1983.
|
|
[GVRLR98]
|
L. Gonzalez-Vega, T. Recio, H. Lombardi, and M.-F. Roy.
Sturm-habicht sequences, determinants and real roots of univariate
polynomials.
In B.F. Caviness and J.R. Johnson, editors, Quantifier
Elimination and Cylindrical Algebraic Decomposition, Texts and Monographs in
Symbolic Computation, pages 300-316. Springer, 1998.
|
|
[Hal04]
|
Dan Halperin.
Arrangements.
In Jacob E. Goodman and Joseph O'Rourke, editors, Handbook of
Discrete and Computational Geometry, chapter 24, pages 529-562. Chapman &
Hall/CRC, 2nd edition, 2004.
|
|
[Han91]
|
E. N. Hanson.
The interval skip list: a data structure for finding all intervals
that overlap a point.
In Proc. 2nd Workshop Algorithms Data Struct., volume 519 of
Lecture Notes Comput. Sci., pages 153-164. Springer-Verlag, 1991.
|
|
[HDD+92]
|
Hugues Hoppe, Tony DeRose, Tom Duchamp, John McDonald, and Werner Stuetzle.
Surface reconstruction from unorganized points.
In Computer Graphics (Proc. SIGGRAPH '90), volume 26, pages
71-77, 1992.
|
|
[HDD+93]
|
H. Hoppe, T. DeRose, T. Duchamp, J. McDonald, and W. Stuetzle.
Mesh optimization.
In Proc. SIGGRAPH '93, pages 19-26, 1993.
|
|
[HGY+99]
|
P. W. Hallinan, G. Gordon, A.L. Yuille, P. Giblin, and D. Mumford.
Two-and Three-Dimensional Patterns of the Face.
A.K.Peters, 1999.
|
|
[HH05]
|
Idit Haran and Dan Halperin.
Efficient point location in cgal arrangements using landmarks, 2005.
|
|
[HM83]
|
S. Hertel and K. Mehlhorn.
Fast triangulation of simple polygons.
In Proc. 4th Internat. Conf. Found. Comput. Theory, volume 158
of Lecture Notes Comput. Sci., pages 207-218. Springer-Verlag, 1983.
|
|
[Hob99]
|
J. D. Hobby.
Practical segment intersection with finite precision output.
Comput. Geom. Theory Appl., 13(4):199-214, October 1999.
|
|
[Hof89a]
|
C. Hoffmann.
Geometric and Solid Modeling.
Morgan-Kaufmann, San Mateo, CA, 1989.
|
|
[Hof89b]
|
C. M. Hoffmann.
The problems of accuracy and robustness in geometric computation.
IEEE Computer, 22(3):31-41, March 1989.
|
|
[Hof89c]
|
Christoph M. Hoffmann.
Geometric and Solid Modeling - An Introduction.
Morgan Kaufmann, 1989.
|
|
[Hof99]
|
M. Hoffmann.
A simple linear algorithm for computing rectangular three-centers.
In Proc. 11th Canad. Conf. Comput. Geom., pages 72-75, 1999.
|
|
[Hof04]
|
Christoph M. Hoffmann.
Solid modeling.
In Jacob E. Goodman and Joseph O'Rourke, editors, Handbook of
Discrete and Computational Geometry, chapter 56, pages 1257-1278. Chapman
& Hall/CRC, 2nd edition, 2004.
|
|
[HP02]
|
D. Halperin and E. Packer.
Iterated snap rounding.
Computational Geometry: Theory and Applications,
23(2):209-225, 2002.
|
|
[HS95]
|
G. R. Hjaltason and H. Samet.
Ranking in spatial databases.
In M. J. Egenhofer and J. R. Herring, editors, Advances in
Spatial Databases - Fourth International Symposium, number 951 in Lecture
Notes Comput. Sci., pages 83-95, August 1995.
|
|
[HS00]
|
Hisamoto Hiyoshi and Kokichi Sugihara.
Voronoi-based interpolation with higher continuity.
In Proc. 16th Annu. ACM Sympos. Comput. Geom., pages 242-250,
2000.
|
|
[HW96]
|
Jed Hartman and Josie Wernecke.
The VRML 2.0 Handbook: Building Moving Worlds on the Web.
Addison-Wesley, 1996.
|
|
[Jar73]
|
R. A. Jarvis.
On the identification of the convex hull of a finite set of points in
the plane.
Inform. Process. Lett., 2:18-21, 1973.
|
|
[Jos99]
|
Nicolai M. Josuttis.
The C++ Standard Library, A Tutorial and Reference.
Addison-Wesley, 1999.
|
|
[Kar04]
|
Menelaos I. Karavelas.
A robust and efficient implementation for the segment Voronoi
diagram.
In Proc. Internat. Symp. on Voronoi diagrams in Science and
Engineering (VD2004), pages 51-62, 2004.
|
|
[KBH05]
|
Michael Kazhdan, M. Bolitho, and Hugues Hoppe.
Poisson Surface Reconstruction.
In Symp. on Geometry Processing, pages 61-70, 2005.
|
|
[KE02]
|
Menelaos I. Karavelas and Ioannis Z. Emiris.
Predicates for the planar additively weighted Voronoi diagram.
Technical Report ECG-TR-122201-01, INRIA Sophia-Antipolis,
Sophia-Antipolis, May 2002.
|
|
[KE03]
|
Menelaos I. Karavelas and Ioannis Z. Emiris.
Root comparison techniques applied to computing the additively
weighted Voronoi diagram.
In Proc. 14th ACM-SIAM Sympos. Discrete Algorithms (SODA),
pages 320-329, 2003.
|
|
[Ker09]
|
Michael Kerber.
Geometric Algorithms for Algebraic Curves and Surfaces.
PhD thesis, Universität des Saarlandes, Saarbrücken, Germany,
2009.
|
|
[Ket98]
|
L. Kettner.
Designing a data structure for polyhedral surfaces.
In Proc. 14th Annu. ACM Sympos. Comput. Geom., pages 146-154,
1998.
|
|
[Ket99]
|
L. Kettner.
Using generic programming for designing a data structure for
polyhedral surfaces.
Comput. Geom. Theory Appl., 13:65-90, 1999.
|
|
[Kha96]
|
L. Khachiyan.
Rounding of polytopes in the real number model of computation.
Mathematics of Operations Research, 21(2):307-320, 1996.
|
|
[Kle89]
|
Rolf Klein.
Concrete and Abstract Voronoi Diagrams, volume 400 of Lecture Notes Comput. Sci.
Springer-Verlag, 1989.
|
|
[KLPY99]
|
Vijay Karamcheti, Chen Li, Igor Pechtchanski, and Chee Yap.
The CORE Library Project, 1.2 edition, 1999.
http://www.cs.nyu.edu/exact/core/.
|
|
[KM76]
|
K. Kuratowski and A. Mostowski.
Set Theory.
North-Holland Publishing Co., 1976.
|
|
[KMP+08]
|
Lutz Kettner, Kurt Mehlhorn, Sylvain Pion, Stefan Schirra, and Chee Yap.
Classroom examples of robustness problems in geometric computations.
Computational Geometry: Theory and Applications, 40(1):61-78,
may 2008.
|
|
[Kob00]
|
Leif Kobbelt.
√3-subdivision.
In Computer Graphics (Proc. SIGGRAPH '00), volume 34, pages
103-112, 2000.
|
|
[KV05]
|
N.G.H. Kruithof and G. Vegter.
Meshing skin surfaces with certified topology.
In Proceedings of the nineth International CADGraphics
conference, page to appear., 2005.
|
|
[KY02]
|
Menelaos Karavelas and Mariette Yvinec.
Dynamic additively weighted voronoi diagrams in 2d.
In Proc. 10th European Symposium on Algorithms, pages 586-598,
2002.
|
|
[Lat91]
|
J.-C. Latombe.
Robot Motion Planning.
Kluwer Academic Publishers, Boston, 1991.
|
|
[LD03]
|
R. G. Laycock and A. M. Day.
Automatically generating roof models from building footprints.
In The 11-th International Conference in Central Europe on
Computer Graphics, Visualization and Computer Vision'2003. Journal of WSCG -
FULL Papers, volume 11, 2003.
|
|
[Lev05]
|
Bruno Levy.
Numerical methods for digital geometry processing.
In Israel Korea Bi-National Conference - Invited talk, extended
abstract (full paper will be available shortly), November 2005.
|
|
[LPRM02]
|
Bruno Lévy, Sylvain Petitjean, Nicolas Ray, and Jérome Maillot.
Least squares conformal maps for automatic texture atlas generation.
In Proceedings of the 29th Conference on Computer Graphics and
Interactive Techniques SIGGRAPH, volume 21(3) of ACM Transactions on
Graphics, pages 362-371, 2002.
|
|
[LPT09]
|
Sylvain Lazard, Luis Peñaranda, and Elias Tsigaridas.
Univariate algebraic kernel and application to arrangements.
In Jan Vahrenhold, editor, SEA, volume 5526 of Lecture
Notes in Computer Science, pages 209-220. Springer, 2009.
|
|
[LS05]
|
Yuanxin Liu and Jack Snoeyink.
A comparison of five implementations of 3D delaunay tessellation.
In János Pach Jacob E. Goodman and Emo Welzl, editors, Combinatorial and Computational Geometry, pages 439-458. MSRI Publications,
2005.
|
|
[LT98]
|
Peter Lindstrom and Greg Turk.
Fast and memory efficient polygonal simplification.
In IEEE Visualization, pages 279-286, 1998.
|
|
[LT99]
|
P. Lindstrom and G. Turk.
Evaluation of memoryless simplification.
IEEE Transactions on Visualization and Computer Graphics,
5(2):98-115, /1999.
|
|
[MAD05]
|
Abdelkrim Mebarki, Pierre Alliez, and Olivier Devillers.
Farthest point seeding for efficient placement of streamlines.
In Proceeding of IEEE Visualization, 2005.
|
|
[Män88]
|
M. Mäntylä.
An Introduction to Solid Modeling.
Computer Science Press, Rockville, MD, 1988.
|
|
[Meh84]
|
Kurt Mehlhorn.
Data Structures and Algorithms 3: Multi-dimensional Searching
and Computational Geometry, volume 3 of EATCS Monographs on Theoretical
Computer Science.
Springer-Verlag, Heidelberg, Germany, 1984.
|
|
[Mel87]
|
A. Melkman.
On-line construction of the convex hull of a simple polyline.
Inform. Process. Lett., 25:11-12, 1987.
|
|
[Mey06]
|
Michal Meyerovitch.
Robust, generic, and efficient constructions of envelopes of surfaces
in three-dimensional space.
Master's thesis, Tel-Aviv University, Israel, 2006.
|
|
[MG06]
|
J. Matoušek and B. Gärtner.
Understanding and Using Linear Programming.
Springer-Verlag, 2006.
|
|
[MN00]
|
Kurt Mehlhorn and Stefan Näher.
LEDA: A Platform for Combinatorial and Geometric Computing.
Cambridge University Press, Cambridge, UK, 2000.
|
|
[MNS+96]
|
Kurt Mehlhorn, Stefan Näher, Thomas Schilz, Stefan Schirra, Michael Seel,
Raimund Seidel, and Christian Uhrig.
Checking geometric programs or verification of geometric structures.
In Proc. 12th Annu. ACM Sympos. Comput. Geom., pages 159-165,
1996.
|
|
[MNSU]
|
K. Mehlhorn, S. Näher, M. Seel, and C. Uhrig.
The LEDA User Manual.
Max-Planck-Insitut für Informatik, 66123 Saarbrücken, Germany.
http://www.mpi-sb.mpg.de/LEDA/leda.html.
|
|
[MP78]
|
D. E. Muller and F. P. Preparata.
Finding the intersection of two convex polyhedra.
Theoret. Comput. Sci., 7:217-236, 1978.
|
|
[MP05]
|
Guillaume Melquiond and Sylvain Pion.
Formal certification of arithmetic filters for geometric predicates.
In Proc. 17th IMACS World Congress on Scientific, Applied
Mathematics and Simulation, 2005.
|
|
[MPFa]
|
MPFI - the multiple precision floating-point interval library.
Revol, Nathalie and Rouillier, Fabrice.
http://perso.ens-lyon.fr/nathalie.revol/software.html.
|
|
[MPFb]
|
MPFR - the multiple precision floating-point reliable library.
The MPFR Team.
http://mpfr.org.
|
|
[MS96]
|
David R. Musser and Atul Saini.
STL Tutorial and Reference Guide: C++ Programming with
the Standard Template Library.
Addison-Wesley, 1996.
|
|
[MSW92]
|
J. Matoušek, Micha Sharir, and Emo Welzl.
A subexponential bound for linear programming.
In Proc. 8th Annu. ACM Sympos. Comput. Geom., pages 1-8, 1992.
|
|
[Mul90]
|
K. Mulmuley.
A fast planar partition algorithm, I.
J. Symbolic Comput., 10(3-4):253-280, 1990.
|
|
[Mye95]
|
Nathan C. Myers.
Traits: a new and useful template technique.
C++ Report, June 1995.
|
|
[OBS04]
|
Yutaka Ohtake, Alexander Belyaev, and Hans-Peter Seidel.
Ridge-valley lines on meshes via implicit surface fitting.
ACM Trans. Graph., 23(3):609-612, 2004.
|
|
[Orl90]
|
M. Orlowski.
A new algorithm for the largest empty rectangle problem.
Algorithmica, 5:65-73, 1990.
|
|
[Ped70]
|
D. Pedoe.
Geometry, a comprehensive course.
Dover Publications, New York, 1970.
|
|
[Pet01]
|
S. Petitjean.
A survey of methods for recovering quadrics in triangle meshes.
ACM Computing Surveys, 34(2), 2001.
|
|
[Phi96]
|
Mark Phillips.
Geomview Manual, Version 1.6.1 for Unix Workstations.
The Geometry Center, University of Minnesota, 1996.
http://www.geom.umn.edu/software/download/geomview.html.
|
|
[Pip93]
|
B. Piper.
Properties of local coordinates based on dirichlet tesselations.
Computing Suppl., 8:227-239, 1993.
|
|
[Por01]
|
I. Porteous.
Geometric Differentiation (2nd Edition).
Cambridge University Press, 2001.
|
|
[PP93]
|
U. Pinkall and K. Polthier.
Computing discrete minimal surfaces and their conjugates.
Experimental Mathematics, 2(1):15-36, 1993.
|
|
[PTVF02]
|
W. Press, S. Teukolsky, W. Vetterling, and B. Flannery.
Numerical Recipes in C++.
Cambridge University Press, 2nd edition, 2002.
|
|
[Pug90]
|
W. Pugh.
Skip lists: a probabilistic alternative to balanced trees.
Commun. ACM, 33(6):668-676, 1990.
|
|
[Req80]
|
Aristides G. Requicha.
Representations for rigid solids: Theory, methods, and systems.
ACM Computing Surveys, 12(4):437-464, 1980.
|
|
[RS]
|
RS - A software for real solving of algebraic systems.
Rouillier, Fabrice.
http://www-salsa.lip6.fr/SALSAWEB/Software.html.
|
|
[RY07]
|
Laurent Rineau and Mariette Yvinec.
A generic software design for Delaunay refinement meshing.
Comput. Geom. Theory Appl., 38:100-110, 2007.
|
|
[RZ04]
|
Fabrice Rouillier and Paul Zimmermann.
Efficient isolation of polynomial's real roots.
Journal of Computational and Applied Mathematics,
162(1):33-50, 2004.
|
|
[Sam90]
|
H. Samet.
The Design and Analysis of Spatial Data Structures.
Addison-Wesley, Reading, MA, 1990.
|
|
[Sch95]
|
O. Schwarzkopf.
The extensible drawing editor Ipe.
In Proceedings of the eleventh annual symposium on Computational
geometry, pages 410-411. ACM New York, NY, USA, 1995.
|
|
[Sch96]
|
Michael Schutte.
Zufällige konvexe mengen.
Master's thesis, Freie Universität Berlin, Germany, 1996.
|
|
[Sch00]
|
Stefan Schirra.
Robustness and precision issues in geometric computation.
In Jörg-Rüdiger Sack and Jorge Urrutia, editors, Handbook of Computational Geometry, chapter 14, pages 597-632. Elsevier
Science Publishers B.V. North-Holland, Amsterdam, 2000.
|
|
[Sei91]
|
R. Seidel.
A simple and fast incremental randomized algorithm for computing
trapezoidal decompositions and for triangulating polygons.
Comput. Geom. Theory Appl., 1(1):51-64, 1991.
|
|
[She98]
|
Jonathan R. Shewchuk.
A condition guaranteeing the existence of higher-dimensional
constrained delaunay triangulations.
In Proc. 14th Annu. ACM Sympos. Comput. Geom., pages 76-85,
1998.
|
|
[She00]
|
Jonathan R. Shewchuk.
Mesh generation for domains with small angles.
In Proc. 16th Annu. ACM Sympos. Comput. Geom., pages 1-10,
2000.
|
|
[Sib80]
|
R. Sibson.
A vector identity for the Dirichlet tesselation.
Math. Proc. Camb. Phil. Soc., 87:151-155, 1980.
|
|
[Sib81]
|
R. Sibson.
A brief description of natural neighbour interpolation.
In Vic Barnet, editor, Interpreting Multivariate Data, pages
21-36. John Wiley & Sons, Chichester, 1981.
|
|
[Sil97]
|
Silicon Graphics Computer Systems, Inc.
Standard template library programmer's guide.
http://www.sgi.com/Technology/STL/, 1997.
|
|
[Skl72]
|
J. Sklansky.
Measuring concavity on rectangular mosaic.
IEEE Trans. Comput., C-21:1355-1364, 1972.
|
|
[SL95]
|
Alexander Stepanov and Meng Lee.
The standard template library.
http://www.cs.rpi.edu/~musser/doc.ps, October 1995.
|
|
[SLL02]
|
Jeremy G. Siek, Lie-Quan Lee, and Andrew Lumsdaine.
Boost Graph Library.
Addison-Wesley, 2002.
|
|
[SM00]
|
M. Seel and K. Mehlhorn.
Infimaximal frames: A technique for making lines look like segments.
Research Report MPI-I-2000-1-005, MPI für Informatik,
Saarbrücken, Germany, December 2000.
http://www.mpi-sb.mpg.de/~mehlhorn/ftp/InfiFrames.ps.
|
|
[SP05]
|
Le-Jeng Shiue and Jörg Peters.
Mesh refinement based on euler encoding.
In Proceedings of the International Conference on Shape Modeling
and Applications 2005, pages 343-348, 2005.
|
|
[STV+95]
|
Christian Schwarz, Jürgen Teich, Alek Vainshtein, Emo Welzl, and Brian L.
Evans.
Minimal enclosing parallelogram with application.
In Proc. 11th Annu. ACM Sympos. Comput. Geom., pages C34-C35,
1995.
|
|
[SW96]
|
Micha Sharir and Emo Welzl.
Rectilinear and polygonal p-piercing and p-center problems.
In Proc. 12th Annu. ACM Sympos. Comput. Geom., pages 122-132,
1996.
|
|
[Tar83]
|
R. E. Tarjan.
Data Structures and Network Algorithms, volume 44 of CBMS-NSF Regional Conference Series in Applied Mathematics.
Society for Industrial and Applied Mathematics, Philadelphia, PA,
1983.
|
|
[Tei99]
|
Monique Teillaud.
Three dimensional triangulations in CGAL.
In Abstracts 15th European Workshop Comput. Geom., pages
175-178. INRIA Sophia-Antipolis, 1999.
|
|
[Ter05]
|
P. Terdiman.
OPCODE 3D Collision Detection library, 2005.
http://www.codercorner.com/Opcode.htm.
|
|
[Tou83]
|
G. T. Toussaint.
Solving geometric problems with the rotating calipers.
In Proc. IEEE MELECON '83, pages A10.02/1-4, 1983.
|
|
[TSA09]
|
Jane TOURNOIS, Rahul SRINIVASAN, and Pierre ALLIEZ.
Perturbing slivers in 3D Delaunay meshes.
In Proceedings of the 18th International Meshing Roundtable,
october 2009.
|
|
[Tut63]
|
W. T. Tutte.
How to draw a graph.
Proceedings London Mathematical Society, 13(52):743-768, 1963.
|
|
[Vai90]
|
A. Vainshtein.
Finding minimal enclosing parallelograms.
Diskretnaya Matematika, 2:72-81, 1990.
In Russian.
|
|
[vLS82]
|
J. van Leeuwen and Anneke A. Schoone.
Untangling a travelling salesman tour in the plane.
In J. R. Mühlbacher, editor, Proc. 7th Internat. Workshop
Graph-Theoret. Concepts Comput. Sci., pages 87-98, München, 1982.
Hanser.
|
|
[VRM96]
|
The virtual reality modeling language specification: Version 2.0, ISO/IEC
CD 14772.
http://www.vrml.org/, August 4 1996.
|
|
[vzGG99]
|
Joachim von zur Gathen and Jürgen Gerhard.
Modern Computer Algebra.
Cambridge University Press, 1999.
|
|
[Wei85]
|
K. Weiler.
Edge-based data structures for solid modeling in a curved surface
environment.
IEEE Comput. Graph. Appl., 5(1):21-40, 1985.
|
|
[Wel91]
|
Emo Welzl.
Smallest enclosing disks (balls and ellipsoids).
In H. Maurer, editor, New Results and New Trends in Computer
Science, volume 555 of Lecture Notes Comput. Sci., pages 359-370.
Springer-Verlag, 1991.
|
|
[Wer94]
|
Josie Wernicke.
The Inventor Mentor: Programming Object-Oriented 3D Graphics
with Open Inventor, Release 2.
Addison-Wesley, 1994.
|
|
[WW02]
|
Joe Warren and Henrik Weimer.
Subdivision Methods for Geometric Design.
Morgan Kaufmann Publishers, New York, 2002.
|
|
[Yap97]
|
C. Yap.
Towards exact geometric computation.
Comput. Geom. Theory Appl., 7(1):3-23, 1997.
|
|
[YD95]
|
C. K. Yap and T. Dubé.
The exact computation paradigm.
In D.-Z. Du and F. K. Hwang, editors, Computing in Euclidean
Geometry, volume 4 of Lecture Notes Series on Computing, pages
452-492. World Scientific, Singapore, 2nd edition, 1995.
|
|
[ZE02]
|
Afra Zomorodian and Herbert Edelsbrunner.
Fast software for box intersection.
Int. J. Comput. Geom. Appl., 12:143-172, 2002.
|