|
[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.
|
|
[AB99] |
Nina Amenta and Marshall Bern.
Surface reconstruction by Voronoi filtering.
Discrete Comput. Geom., 22(4):481-504, 1999.
|
|
[ADS98] |
Pierre Alliez, Olivier Devillers, and Jack Snoeyink.
Removing degeneracies by perturbing the problem or the world.
In Proc. 10th Canad. Conf. Comput. Geom., 1998.
|
|
[AKM87] |
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.
|
|
[BDP02] |
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.
|
|
[BEH02] |
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.
|
|
[Ben75] |
J. L. Bentley.
Multidimensional binary search trees used for associative searching.
Commun. ACM, 18(9):509-517, September 1975.
|
|
[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.
|
|
[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.
|
|
[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.
|
|
[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.
|
|
[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.
|
|
[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.
|
|
[Edd77] |
W. F. Eddy.
A new convex hull algorithm for planar sets.
ACM Trans. Math. Softw., 3:398-403 and 411-412, 1977.
|
|
[EDD95] |
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 file://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.
|
|
[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.
|
|
[EKP04] |
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.
|
|
[EM94] |
H. Edelsbrunner and E. P. Mücke.
Three-dimensional alpha shapes.
ACM Trans. Graph., 13(1):43-72, January 1994.
|
|
[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.
|
|
[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 th paths and -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.
|
|
[GHH03] |
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://www.swox.com/gmp/.
|
|
[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.
|
|
[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.
|
|
[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.
|
|
[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.
|
|
[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.
|
|
[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.
|
|
[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.
|
|
[Kob00] |
Leif Kobbelt.
-subdivision.
In Computer Graphics (Proc. SIGGRAPH '00), volume 34, pages
103-112, 2000.
|
|
[KY02] |
Menelaos Karavelas and Mariette Yvinec.
Dynamic additively weighted voronoi diagrams in 2d.
In Proc. 10th European Symposium on Algorithms, pages 586-598,
2002.
|
|
[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.
|
|
[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.
|
|
[MN00] |
Kurt Mehlhorn and Stefan Näher.
LEDA: A Platform for Combinatorial and Geometric Computing.
Cambridge University Press, Cambridge, UK, 2000.
|
|
[MNS96] |
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.
|
|
[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.
|
|
[Orl90] |
M. Orlowski.
A new algorithm for the largest empty rectangle problem.
Algorithmica, 5:65-73, 1990.
|
|
[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.
|
|
[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.
|
|
[RY06] |
Laurent Rineau and Mariette Yvinec.
A generic software design for Delaunay refinement meshing.
to be published, 2006.
|
|
[Sam90] |
H. Samet.
The Design and Analysis of Spatial Data Structures.
Addison-Wesley, Reading, MA, 1990.
|
|
[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.
|
|
[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.
|
|
[STV95] |
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 -piercing and -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.
|
|
[Tou83] |
G. T. Toussaint.
Solving geometric problems with the rotating calipers.
In Proc. IEEE MELECON '83, pages A10.02/1-4, 1983.
|
|
[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.
|
|
[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.
|