Algorithms Lab

Currently, we are interested in designing algorithms and data structures that could solve various problems in dynamic environments. The problems that we are interested include nearest neighbor search, point location, Voronoi diagram, and convex hull. We seek to find ways to extend already known efficient algorithms in static environments to work in dynamic environments. Also, we are applying algorithms in computational geometry to solve various geometric problems in the practical world, such as navigation system, teeth alignment, and semiconductor design. Geometric Shape Matching is an important ingredient in shape retrieval, recognition and classification, alignment and registration, and approximation and simplification. In a large database of shapes, for example, shape retrieval searches for all shapes similar to a query shape. Unfortunately many of these problems turn out to be computationally difficult. Many of them areNP-hard, and for many others the best known solutions have polynomial runtimes of high degree which renders these algorithms uninteresting from a practical point of view. A possible solution is that instead of insisting on computing the exact solution for such an optimization problem, one looks for a solution that approximates the optimum reasonably well. Skyline queries have gained much attention lately in database and data mining communities, as formulating such queries is rather intuitive compared to other types of queries, for example, ranking. However, not much has been known about Spatial Skyline Queries, skyline queries on massive spatial data. We study spatial skyline query processing problem, which enables an intelligent and efficient access to massive spatial data. In Casting, liquid is poured into a cast that has a cavity with the shape of