EFFECTIVE COMPUTATIONAL GEOMETRY FOR CURVES AND SURFACES
CONTENTS 1 ARRANGEMENTS E?FOGEL, DAN HALPERIN?, LUTZ KETTNER, MONIQUE TEILLAUD, RON WEIN, NICOLA WOLPERT 1 1 INTRODUCTION 1 2 CHRONICLES 1 3 EXACT CONSTRUCTION OF PLANAR ARRANGEMENTS 1 3 1 CONSTRUCTION BY SWEEPING 1 3 2 INCREMENTAL CONSTRUCTION 1 4 SOFTWARE FOR PLANAR ARRANGEMENTS 1 4 1 THE CGAL ARRANGEMENTS PACKAGE 1 4 2 ARRANGEMENTS TRAITS 1 4 3 TRAITS CLASSES FROM EXACUS 1 4 4 AN EMERGING CGAL CURVED KERNEL 1 4 5 HOW TO SPEED UP YOUR ARRANGEMENT COMPUTATION IN CGAL 1 5 EXACT CONSTRUCTION IN 3-SPACE 1 5 1 SWEEPING ARRANGEMENTS OF SURFACES 1 5 2 ARRANGEMENTS OF QUADRICS IN 3D 1 6 CONTROLLED PERTURBATION: FIXED-PRECISION APPROXIMATION OF ARRANGEMENTS 1 7 APPLICATIONS 1 7 1 BOOLEAN OPERATIONS ON GENERALIZED POLYGONS 1 7 2 MOTION PLANNING FOR DISCS 1 7 3 LOWER ENVELOPES FOR PATH VERI?CATION IN MULTI-AXIS NC-MACHINING 1 7 4 MAXIMAL AXIS-SYMMETRIC POLYGON CONTAINED IN A SIMPLE POLYGON 1 7 5 MOLECULAR SURFACES 1 7 6 ADDITIONAL APPLICATIONS 1 8 FURTHER READING AND OPEN PROBLEMS 2 CURVED VORONOI DIAGRAMS JEAN-DANIEL BOISSONNAT?, CAMILLE WORMSER, MARIETTE YVINEC 2 1 INTRODUCTION 2 2 LOWER ENVELOPES AND MINIMIZATION DIAGRAMS 2 3 A?NE VORONOI DIAGRAMS 2 3 1 EUCLIDEAN VORONOI DIAGRAMS OF POINTS 2 3 2 DELAUNAY TRIANGULATION 2 3 3 POWER DIAGRAMS 2 4 VORONOI DIAGRAMS WITH ALGEBRAIC BISECTORS 2 4 1 M¨OBIUS DIAGRAMS 2 4 2 ANISOTROPIC DIAGRAMS 2 4 3 APOLLONIUS DIAGRAMS 2 5 LINEARIZATION 2 5 1 ABSTRACT DIAGRAMS 2 5 2 INVERSE PROBLEM 2 6 INCREMENTAL VORONOI ALGORITHMS 2 6 1 PLANAR EUCLIDEAN DIAGRAMS 2 6 2 INCREMENTAL CONSTRUCTION 2 6 3 THE VORONOI HIERARCHY 2 7 MEDIAL AXIS 2 7 1 MEDIAL AXIS AND LOWER ENVELOPE 2 7 2 APPROXIMATION OF THE MEDIAL AXIS 2 8 VORONOI DIAGRAMS IN CGAL 2 9 APPLICATIONS 3 ALGEBRAIC ISSUES IN COMPUTATIONAL GEOMETRY BERNARD MOURRAIN?, SYLVAIN PION, SUSANNE SCHMITT, JEAN-PIERRE T´ECOURT, ELIAS TSIGARIDAS, NICOLA WOLPERT 3 1 INTRODUCTION 3 2 COMPUTERS AND NUMBERS 3 2 1 MACHINE FLOATING POINT NUMBERS: THE IEEE 754 NORM 3 2 2 INTERVAL ARITHMETIC 3 2 3 FILTERS 3 3 E?ECTIVE REAL NUMBERS 3 3 1 ALGEBRAIC NUMBERS 3 3 2 ISOLATING INTERVAL REPRESENTATION OF REAL ALGEBRAIC NUMBERS 3 3 3 SYMBOLIC REPRESENTATION OF REAL ALGEBRAIC NUMBERS 3 4 COMPUTING WITH ALGEBRAIC NUMBERS 3 4 1 RESULTANT 3 4 2 ISOLATION 3 4 3 ALGEBRAIC NUMBERS OF SMALL DEGREE 3 4 4 COMPARISON 3 5 MULTIVARIATE PROBLEMS 3 6 TOPOLOGY OF PLANAR IMPLICIT CURVES 3 6 1 THE ALGORITHM FROM A GEOMETRIC POINT OF VIEW 3 6 2 ALGEBRAIC INGREDIENTS 3 6 3 HOW TO AVOID GENERICITY CONDITIONS 3 7 TOPOLOGY OF 3D IMPLICIT CURVES 3 7 1 CRITICAL POINTS AND GENERIC POSITION 3 7 2 THE PROJECTED CURVES 3 7 3 LIFTING A POINT OF THE PROJECTED CURVE 3 7 4 COMPUTING POINTS OF THE CURVE ABOVE CRITICAL VALUES 3 7 5 CONNECTING THE BRANCHES 3 7 6 THE ALGORITHM 3 8 SOFTWARE 4 DI?ERENTIAL GEOMETRY ON DISCRETE SURFACES DAVID COHEN-STEINER, JEAN-MARIE MORVAN? 4 1 GEOMETRIC PROPERTIES OF SUBSETS OF POINTS 4 2 LENGTH AND CURVATURE OF A CURVE 4 2 1 THE LENGTH OF CURVES 4 2 2 THE CURVATURE OF CURVES 4 3 THE AREA OF A SURFACE 4 3 1 DE?NITION OF THE AREA 4 3 2 AN APPROXIMATION THEOREM 4 4 CURVATURES OF SURFACES 4 4 1 THE SMOOTH CASE 4 4 2 POINTWISE APPROXIMATION OF THE GAUSSIAN CURVATURE 4 4 3 FROM POINTWISE TO LOCAL 4 4 4 ANISOTROPIC CURVATURE MEASURES 4 4 5 ?-SAMPLES ON A SURFACE 4 4 6 APPLICATION 5 MESHING OF SURFACES JEAN-DANIEL BOISSONNAT, DAVID COHEN-STEINER, BERNARD MOURRAIN, G¨UNTER ROTE?, GERT VEGTER 5 1 INTRODUCTION: WHAT IS MESHING? 5 1 1 OVERVIEW 5 2 MARCHING CUBES AND CUBE-BASED ALGORITHMS 5 2 1 CRITERIA FOR A CORRECT MESH INSIDE A CUBE 5 2 2 INTERVAL ARITHMETIC FOR ESTIMATING THE RANGE OF A FUNCTION 5 2 3 GLOBAL PARAMETERIZABILITY: SNYDER’S ALGORITHM 5 2 4 SMALL NORMAL VARIATION 5 3 DELAUNAY RE?NEMENT ALGORITHMS 5 3 1 USING THE LOCAL FEATURE SIZE 5 3 2 USING CRITICAL POINTS 5 4 A SWEEP ALGORITHM 5 4 1 MESHING A CURVE 5 4 2 MESHING A SURFACE 5 5 OBTAINING A CORRECT MESH BY MORSE THEORY 5 5 1 SWEEPING THROUGH PARAMETER SPACE 5 5 2 PIECEWISE-LINEAR INTERPOLATION OF THE DE?NING FUNCTION 5 6 RESEARCH PROBLEMS 6 DELAUNAY TRIANGULATION BASED SURFACE RECONSTRUCTION FR´ED´ERIC CAZALS, JOACHIM GIESEN 6 1 INTRODUCTION 6 1 1 SURFACE RECONSTRUCTION 6 1 2 APPLICATIONS 6 1 3 RECONSTRUCTION USING THE DELAUNAY TRIANGULATION 6 1 4 A CLASSI?CATION OF DELAUNAY BASED SURFACE RECONSTRUCTION METHODS 6 1 5 ORGANIZATION OF THE CHAPTER 6 2 PREREQUISITES 6 2 1 DELAUNAY TRIANGULATIONS, VORONOI DIAGRAMS AND RELATED CONCEPTS 6 2 2 MEDIAL AXIS AND DERIVED CONCEPTS 6 2 3 TOPOLOGICAL AND GEOMETRIC EQUIVALENCES 6 2 4 EXERCISES 6 3 OVERVIEW OF THE ALGORITHMS 6 3 1 TANGENT PLANE BASED METHODS 6 3 2 RESTRICTED DELAUNAY BASED METHODS 6 3 3 INSIDE / OUTSIDE LABELING 6 3 4 EMPTY BALLS METHODS 6 4 EVALUATING SURFACE RECONSTRUCTION ALGORITHMS 6 5 SOFTWARE 6 6 RESEARCH PROBLEMS 7 COMPUTATIONAL TOPOLOGY: AN INTRODUCTION G¨UNTER ROTE, GERT VEGTER? 7 1 INTRODUCTION 7 2 SIMPLICIAL COMPLEXES 7 3 SIMPLICIAL HOMOLOGY 7 4 MORSE THEORY 7 4 1 SMOOTH FUNCTIONS AND MANIFOLDS 7 4 2 BASIC RESULTS FROM MORSE THEORY 7 5 EXERCISES 8 APPENDIX - GENERIC PROGRAMMING AND THE CGAL LIBRARY E?FOGEL, MONIQUE TEILLAUD 8 1 THE CGAL OPEN SOURCE PROJECT 8 2 GENERIC PROGRAMMING 8 3 GEOMETRIC PROGRAMMING AND CGAL 8 4 CGAL CONTENTS REFERENCES