Proximity Introduction Comments We consider in this topic a large class of related problems that deal with proximity of points in the plane We will 1 Define some proximity problems and see how they are related 2 Study a classic algorithm for one of the problems 3 Introduce triangulations 4 Examine a data structure that seems to represent nearly everything we might like to know about proximity in a set of points in the plane Overview of the topic Subtopic Collection of proximity problems Closest pair divide and conquer algorithm Triangulations Problem definitions Greedy algorithm Constrained triangulations Triangulating polygons Voronoi diagrams Definition Properties Construction Delaunay triangulations Proximity problems and Voronoi diagrams Source P5 1 P5 3 P5 4 P6 2 O1 P5 5 O5 3 P5 6 Proximity Proximity problems Closest pair CLOSEST PAIR INSTANCE Set S p1 p2 pN of N points in the plane QUESTION Determine the two points of S whose mutual distance is smallest Distance is defined as the usual Euclidean distance distance pi pj sqrt xi xj 2 yi yj 2 This problem is described as one of the fundamental questions of computational geometry in Preparata Brute force A brute force solution is to compute the distance for every pair of points saving the smallest this requires O dN2 time The factor d is the number of dimensions i e the number of coordinates involved in each distance computation For d 1 we can do better than O N2 as follows 1 Sort the N points which are simply numbers O N log N 2 Scan the sorted sequence x1 x2 xN computing xi 1 xi for i 1 2 N 1 Save the smallest difference This is optimal for d 1 For d 2 can we do better than O 2N2 O N2 Proximity Proximity problems All nearest neighbors ALL NEAREST NEIGHBORS INSTANCE Set S p1 p2 pN of N points in the plane QUESTION Determine the nearest neighbor point of minimum distance for each point in S Proximity Proximity problems Nearest neighbor relation 1 Nearest neighbor is a relation on a set S as follows point b is a nearest neighbor of point a denoted a b if distance a b min distance a c c S a a b c S The nearest neighbor relation is not symmetric i e a b does not imply b a though it could be true Preparata p 186 says Note also that a point is not the nearest neighbor of a unique point i e is not a function Perhaps slightly clearer Note that a point is not necessarily the nearest neighbor of a unique point i e is not one to one nor is it onto as a point may have more than one nearest neighbor Proximity Proximity problems Nearest neighbor relation 2 Footnote 2 on Preparata p 186 Although a point can be the nearest neighbor of every other point a point can have at most six nearest neighbors in two dimensions Point c has every other point as its nearest neighbor At most six points can have point c as their nearest neighbor I think that is backwards and should be Although a point can have every other point as a nearest neighbor a point can be the nearest neighbor of at most six other points in two dimensions c Proximity Proximity problems Euclidean minimum spanning tree EUCLIDEAN MINIMUM SPANNING TREE INSTANCE Set S p1 p2 pN of N points in the plane QUESTION Construct a tree of minimum total length whose vertices are the points in S A solution to this problem will be the N 1 pairs of points in S that comprise the edges of the tree The more general Minimum Spanning Tree MST problem is usually formulated as a problem in graph theory Given a graph G with N nodes and E weighted edges find the subtree of G that includes every vertex with minimum total edge weight In the Euclidean Minimum Spanning Tree EMST problem the equivalent graph formulation has graph G complete i e every pair of vertices is joined by an edge with the edges weights just the distance between the vertices Any algorithm that attacks EMST as a graph problem must necessarily take O N2 time because a MST on a graph must contain a shortest edge and to find the shortest edge of the graph G using a graph approach requires examining N2 edges We seek a geometric algorithm for EMST that requires O N2 time Proximity Proximity problems Triangulation TRIANGULATION INSTANCE Set S p1 p2 pN of N points in the plane QUESTION Join the points in S with nonintersecting straight line segments so that every region internal to the convex hull of S is a triangle A triangulation for a set S is not necessarily unique As a planar graph a triangulation on N vertices has 3N 6 edges Proximity Proximity problems Single shot vs search The previous problems CLOSEST PAIR ALL NEAREST NEIGHBORS EUCLIDEAN MINIMUM SPANNING TREE and TRIANGULATION have been single shot We now define two search type proximity problems Because these are search problems repetitive mode is assumed and thus preprocessing is allowed Nearest neighbor search NEAREST NEIGHBOR SEARCH INSTANCE Set S p1 p2 pN of N points in the plane QUESTION Given a query point q which point p S is a nearest neighbor of q p q Proximity Proximity problems k nearest neighbors k NEAREST NEIGHBORS INSTANCE Set S p1 p2 pN of N points in the plane QUESTION Given a query point q determine the k points of S nearest to q This problem is equivalent to the previous one for k 1 The figure gives the solution for k 3 q Proximity Proximity problems Element uniqueness Preparata defines a computational prototype as an archetypal problem one which can act as a fundamental representative for a class of problems For example SATISFIABILITY for NP complete problems or SORTING from many problems in computational geometry Another such problem is ELEMENT UNIQUENESS ELEMENT UNIQUENESS INSTANCE Set S x1 x2 xN of N real numbers QUESTION Are any two numbers xi xj in S equal It is shown in the text Preparata p 192 using the algebraic decision tree model that a lower bound on time for ELEMENT UNIQUENESS is in N log N Three problems SORTING ELEMENT UNIQUENESS and EXTREME POINTS Preparata p 99 all have lower bounds on time in N log N However they are not easily transformable reducible to each other Preparata asks do they have a common ancestor problem that can be transformed into all of them O N SORTING O N O N ELEMENT UNIQUENESS EXTREME POINTS Proximity Proximity problems Lower bounds The proximity problems we have defined can be transformed into each other as follows ELEMENT UNIQUENESS O N CLOSEST PAIR N log N ALL NEAREST NEIGHBORS O N SORTING O N EUCLIDEAN MINIMUM SPANNING TREE O N TRIANGULATION N log N BINARY SEARCH O N O 1 NEAREST NEIGHBOR SEARCH O 1 k NEAREST NEIGHBORS log N Here