# Algorithms for proximity problems in the presence of obstacles

Abstract (Summary)

(Uncorrected OCR) Abstract of Thesis Entitled \Algorithms for Proximity Problems in the Presence of Obstacles" Submitted by Vivian Mak For the Degree of Master of Philosophy at the University of Hong Kong in August 1999 The nearest neighbour problem is one of the fundamental problems in computational geometry. In this problem, a set of n points in a geometric space is given and we have to store it in a data structure such that given a query point, we can efficiently find a point from the set which is nearest to the query point. This problem has been extensively studied and appears in applications like information retrieval, data compression, pattern recognition and multimedia databases. In this thesis, we studied the dynamic nearest neighbour problem where the points are on a plane in the presence of a set of k disjoint obstacles. In this problem, points are inserted and deleted and we have to maintain the data structure for the nearest neighbour query after the set is updated. We presented an algorithm for maintaining a data structure that can answer queries of a 2-approximate neighbour when the points are on a plane with a set of polygonal obstacles with distances measured in the rectilinear metric. A point q is called a c-approximate neighbour of a point p if d(p; q) < c ?d(p;p*) where p* is the true nearest neighbour of p. This algorithm can also answer queries of a 2 p 2-approximate neighbour with distances measured in the Euclidean metric. Moreover, we also considered the restricted case of vertical line obstacles and showed that given such a restricted case, we can answer the queries much faster than in the case of polygonal obstacles if we allow for a larger approximation ratio. We gave a data structure and an algorithm to find a 3-approximate neighbour in this case for the rectilinear metric. The closest pair problem is another basic problem in computational geometry. In the closest pair problem, we are given a set of n points in a geometric space and we want to find a pair of distinct points (p; q) such that the distance between the pair d(p; q) is minimum among all pairs of points and report the distance between them. The problem arises naturally in many applications and has been extensively studied. In this thesis, we studied the dynamic closest pair problem where the points are on a plane in the presence of a set of k disjoint obstacles. In this problem, points are inserted and deleted and we have to maintain the closest pair after the set is updated. We studied the problem for different kinds of obstacles such as rectangular, rectilinear and polygonal obstacles and presented algorithms for maintaining the closest pair for each case when the distance metric used is i the rectilinear metric. The algorithms can also maintain the 2-approximate closest pair when the distance metric used is the Euclidean metric. A pair of points s and t is called a c-approximate closest pair if d(s; t) < c ?d(p; q) where (p; q) is the true closest pair. Another contribution of this thesis is an approximation algorithm for the online version of the closest pair problem, where only point insertions are allowed. We showed that with preprocessing, we can maintain the 6-approximate closest pair upon insertions of points in a much faster way compared to the dynamic case. ii
Bibliographical Information:

Advisor:

School:The University of Hong Kong

School Location:China - Hong Kong SAR

Source Type:Master's Thesis

Keywords:data structures computer science geometry processing

ISBN:

Date of Publication:01/01/2000