February 1, 2005 Lecture 1: Introduction to Geometric ComputationGeometric Computation: IntroductionPiotr IndykFebruary 1, 2005 Lecture 1: Introduction to Geometric ComputationWelcome to 6.838 !• Overview and goals• Course Information• 2D Convex hull• Signup sheetFebruary 1, 2005 Lecture 1: Introduction to Geometric ComputationGeometric Computation • Geometric computation occurs everywhere:– Robotics: motion planning, map construction and localization– Geographic Information Systems (GIS): range search, nearest neighbor– Simulation: collision detection– Computer graphics: visibility tests for rendering– Computer vision: pattern matching– Computational drug design: spatial indexingFebruary 1, 2005 Lecture 1: Introduction to Geometric ComputationComputational Geometry• Started in mid 70’s• Focused on design and analysis of algorithms for geometric problems• Many problems well-solved, e.g., Voronoidiagrams, convex hulls• Many other problems remain openFebruary 1, 2005 Lecture 1: Introduction to Geometric ComputationCourse Goals• Introduction to Computational Geometry– Well-established results and techniques– New directionsFebruary 1, 2005 Lecture 1: Introduction to Geometric ComputationSyllabus• Part I - Classic CG:– 2D Convex hull– Segment intersection– LP in low dimensions– Polygon triangulation– Range searching– Point location– Arrangements and duality– Voronoi diagrams– Delaunay triangulations– Binary space partitions– Motion planning and Minkowski sumUse “Computational Geometry: Algorithms and Applications” by de Berg, van Kreveld, Overmars, Schwarzkopf (2ndedition).February 1, 2005 Lecture 1: Introduction to Geometric ComputationSyllabus ctd.• Part II - New directions:– LP in higher dimensions– Closest pair in low dimensions– Approximate nearest neighbor in low dimensions– Approximate nearest neighbor in high dimensions: LSH– Low-distortion embeddings– Low-distortion embeddings II– Geometric algorithms for external memory – Geometric algorithms for streaming data– Kinetic algorithms– Pattern matching– Combinatorial geometry– Geometric optimization– ConclusionsFebruary 1, 2005 Lecture 1: Introduction to Geometric ComputationHigher dimensions - eigenfaces=?February 1, 2005 Lecture 1: Introduction to Geometric ComputationCourse Information• 3-0-9 H-level Graduate Credit• Grading:– 4 problem sets (see calendar):– In each PSet:• Core component (mandatory): 6.046-style• Two optional components:– More theoretical problems– Java programming assignments– Can collaborate, but solutions written separately– No midterm/final J• Prerequisites: understanding of algorithms and probability (6.046 level)February 1, 2005 Lecture 1: Introduction to Geometric ComputationQuestions ?February 1, 2005 Lecture 1: Introduction to Geometric ComputationConvexity• A set is convex if every line segment connecting two points in the set is fully contained in the setFebruary 1, 2005 Lecture 1: Introduction to Geometric ComputationConvex hull• What is a convex hull of a set of points P ?– Smallest convex set containing P– Union of all points expressible by a convex combination of points in P, i.e. points p of the formp∈Pcp*p, cp0, p∈Pcp=1• Definitions not suitable for an algorithmFebruary 1, 2005 Lecture 1: Introduction to Geometric ComputationComputational Problem• Given P⊂R2, |P|=n, find the description of CH(P)– CH(P) is a convex polygon with at most n vertices– We want to find those vertices in clockwise order• Design fast algorithm for this problem• We assume all points are distinct (otherwise can sort and remove duplicates)• Any algorithms ?February 1, 2005 Lecture 1: Introduction to Geometric ComputationSimple approachpqpqFebruary 1, 2005 Lecture 1: Introduction to Geometric ComputationSimple approach1. For all pairs (p,q) of points in P/* Check if p q forms a boundary edge */A. For all points r∈P-{p,q}:– If r lies to the left of directed line p q, then go to Step 2B. Add (p,q) to the set of edges E2. Endfor3. Order the edges in E to form the boundary of CH(P)February 1, 2005 Lecture 1: Introduction to Geometric ComputationDetails• How to test if r lies to the left of a directed line p q ?– Basic geometric operation– Reduces to checking the sign of a certain determinant– Constant time operationFebruary 1, 2005 Lecture 1: Introduction to Geometric ComputationAnalysis• Outer loop: O(n2) repetitions• Inner loop: O(n) repetitions• Total time: O(n3)February 1, 2005 Lecture 1: Introduction to Geometric ComputationProblems• Running time pretty high• Algorithm can do strange things:– What 3 points are collinear ? (degeneracy)– What 3 points are near-collinear ? (robustness)February 1, 2005 Lecture 1: Introduction to Geometric ComputationCollinear pointsFebruary 1, 2005 Lecture 1: Introduction to Geometric ComputationNearly collinear pointsFebruary 1, 2005 Lecture 1: Introduction to Geometric ComputationProblems• Issues:– Degeneracy: input is “special”– Robustness: implementation makes round-off errors• Solutions:– Degeneracy: correct algorithm design– Robustness: higher/arbitrary precision• Our solution: typically, sweep the issue under the carpetFebruary 1, 2005 Lecture 1: Introduction to Geometric ComputationAndrews algorithm• Convexify(S,p)– While t=|S| 2 and p left of line st-1st, remove stfrom S– Add p to the end of S• Incremental-Hull(P)– Sort P by x-coordinates– Create U={p1}– For i=2 to n• Convexify(U,pi)– Create L={pn}– For i=n-1 downto 1• Convexify(L,pi)– Remove first/last point of L, output U and LFebruary 1, 2005 Lecture 1: Introduction to Geometric ComputationAnimationDaniel Vlasic's CH AnimationFebruary 1, 2005 Lecture 1: Introduction to Geometric ComputationIssues• Points with the same x-coordinate• Modification: Sort by x and then by y• Solves the degeneracy problem• Robustness:– Still an issue– But the algorithm outputs closed polygonal chainFebruary 1, 2005 Lecture 1: Introduction to Geometric ComputationAnalysis• Sorting: O(n log n)• Incremental walk: O(n)• Altogether: O(n log