Survey and Recent Results: Robust Geometric ComputationOVERVIEWNumerical Nonrobustness PhenomenonPart I: OVERVIEWNumerical Non-robustnessExamplesResponses to Non-robustnessImpact of Non-robustnessWhat is Special about Geometry?Geometry is HarderExample: Convex HullsConsistencyExamples/NonexamplesTaxonomy of ApproachesGold StandardType I ApproachesExampleExampleSlide 19Exact ApproachAlgebraic ComputationType II ApproachConsistency ApproachConsistency is HardExact Geometric ComputationPart II: OVERVIEWHow to Compute Exactly in the Geometric SenseExact Geometric Computation (EGC)Constant ExpressionsFundamental Problem of EGCComplexity of CSPRoot BoundHow to use root boundsNominally Exact InputsCore LibraryEGC LibrariesSlide 37Core Accuracy APIDelivery SystemWhat is in CORE levels?What is in Level III?Relative and Absolute PrecisionPrecision-Driven Eval of ExpressionsSlide 44Example: Theorem Proving ApplicationConstructive Root BoundsProblem of Constructive Root BoundsIllustrationDegree-Measure BoundsBFMS BoundNew Constructive BoundInductive RulesComparative StudyExperimental ResultsTiming on Synthetic InputTiming for Degenerate inputMoore’s Law and Non-robustness TrendsPart III: OVERVIEWMoore’s Law and RobustnessReversing the TrendRobustness Trade-off CurvesComputing on the CurveArchitectureHardware Change/UpgradeCertification ParadigmAnother Paradigm ShiftVerification vs. CheckingChecking vs. CertifyingFiltered AlgorithmsSome Floating Point FiltersModel for FilteringExtensionsConclusionREVIEWSummaryDownload SoftwareLast SlideExtrasAlgebraic Degree BoundLeading Coefficients and Conjugates Bound(cont.)End of Extra SlidesOct 18, 2001 Talk @ MIT 1Survey and Recent Results: Robust Geometric ComputationChee YapDepartment of Computer ScienceCourant InstituteNew York UniversityOct 18, 2001 Talk @ MIT 2 OVERVIEWPart I: NonRobustness SurveyPart II: Exact Geometric ComputationCore LibraryConstructive Root BoundsPart III: New DirectionsMoore’s Law and NonRobustnessCertification ParadigmConclusionOct 18, 2001 Talk @ MIT 3Numerical Nonrobustness PhenomenonOct 18, 2001 Talk @ MIT 4Part I: OVERVIEWThe PhenomenonWhat is Geometric?Taxonomy of ApproachesEGC and relativesOct 18, 2001 Talk @ MIT 5Numerical Non-robustnessNon-robustness phenomenoncrash, inconsistent state, intermittentRound-off errorsbenign vs. catastrophicquantitative vs. qualitativeOct 18, 2001 Talk @ MIT 6ExamplesIntersection of 2 linescheck if intersection point is on line Mesh Generationpoint classification error (dirty meshes) Trimmed algebraic patches in CADbounding curves are approximated leading to topological inconsistenciesFront Tracking Physics Simulationfront surface becomes self-intersectingOct 18, 2001 Talk @ MIT 7Responses to Non-robustness“It is a rare event”“Use more stable algorithms”“Avoid ill-conditioned inputs”“Epsilon-tweaking”“There is no solution”“Our competitors couldn’t do it, so we don’t have to bother”Oct 18, 2001 Talk @ MIT 8Impact of Non-robustnessAcknowledged, seldom demandedEconomic/productivity Impactbarrier to full automationscientist/programmer productivitymission critical computation failPatriot missile, Ariadne RocketE.g. Mesh generationa preliminary step for simulations1 failure/5 million cells [Aftosmis]tweak data if failureOct 18, 2001 Talk @ MIT 9What is Special about Geometry?Oct 18, 2001 Talk @ MIT 10Geometry is HarderGeometry = Combinatorics+NumericsE.g. Voronoi DiagramOct 18, 2001 Talk @ MIT 11Example: Convex Hulls2121334 45 566778899Input Convex Hull Output2134567Oct 18, 2001 Talk @ MIT 12Consistency Geometric ObjectConsistency Relation (P)E.g. D is convex hull or Voronoi diagramQualitative error  inconsistencyD = (G, L,P)G=graph, L=labeling of GOct 18, 2001 Talk @ MIT 13Examples/NonexamplesConsistency is criticalmatrix multiplicationshortest paths in graphs (e.g. Djikstra’s algorithm)sorting and geometric sortingEuclidean shortest pathsOct 18, 2001 Talk @ MIT 14Taxonomy of ApproachesOct 18, 2001 Talk @ MIT 15Gold StandardMust understand the dominant mode of numerical computing“F.P. Mode” :machine floating pointfixed precision (single/double/quad)IEEE 754 Standard What does the IEEE standard do for nonrobustness? Reduces but not eliminate it. Main contribution is cross-platform pre dictability.Historical NoteOct 18, 2001 Talk @ MIT 16Type I ApproachesBasic Philosophy: to make the fast but imprecise (IEEE) arithmetic robustTaxonomyarithmetic (FMA, scalar vector, sli, etc) finite resolution predicates (-tweaking, -predicates [Guibas-Salesin-Stolfi’89])finite resolution geometry (e.g., grids)topology oriented approach [Sugihara-Iri’88]Oct 18, 2001 Talk @ MIT 17Example Grid Geometry [Greene-Yao’86]Finite Resolution GeometriesOct 18, 2001 Talk @ MIT 18ExampleWhat is a Finite Resolution Line?A suitable set of pixels [graphics]A fat line [generalized intervals]A polyline [Yao-Greene, Milenkovic, etc]A rounded line [Sugihara]fat line:polyline:aX+bY+c=0; (a<2L, b<2L, c<22L)rounded line:Oct 18, 2001 Talk @ MIT 19ExampleTopology Oriented Approach of Sugihara-Iri: Voronoi diagram of 1 million pointsPriority of topological part over numerical partIdentify relevant and maintainable properties: e.g. planarityIssue: which properties to choose?Oct 18, 2001 Talk @ MIT 20Exact ApproachIdea: avoid all errorsBig number packages (big integers, big rationals, big floats, etc)Only rational problems are exactEven this is a problem [Yu’92, Karasick-Lieber-Nackman’89]Oct 18, 2001 Talk @ MIT 21Algebraic ComputationAlgebraic number:   2   1 4142P(x) = x2 – 2 = 0Representation:   P(x), 1, 2)Exact manipulation:comparisonarithmetic operations, roots, etc.Most problems in Computational Geometry textbooks requires only+, –, , , Oct 18, 2001 Talk @ MIT 22Type II ApproachBasic Philosophy: to make slow but error-free computation more efficientTaxonomyExact Arithmetic (naïve approach)Expression packagesCompiler techniquesConsistency approachExact Geometric Computation (EGC)Oct 18, 2001 Talk @ MIT 23Consistency ApproachGoal: ensure that no decisions are contradictoryParsimonious Algorithms [Fortune’89] : only make tests that