Exercises

1. Define convex hull. Is it possible to have convex-hull of two dimensional space? Can it exists in $k-$dimensional space $\Re^k$, where $k > 2$? Justify your answer.

2. What are the different algorithms to find out convex-hull in Euclidean space $\Re^k$ for $k=2$ for set of points $\vert S\vert = n$? Write the steps for each algorithm and compute their time complexity.

3. What is meant by proximity in a set of points $\vert S\vert = n$ in Euclidean space $\Re^k$ for $k=2$? What may be the applications of computing the proximity?

4. Explain Voronoi diagrams and discuss their applications.