Lectures:
The complexity of a problem and the complexity of an algorithm. The complexity in the worst case, expected complexity. Models of computation. RAM, algebraic decision tree.
Estimating the lower bound of the worst case time complexity by making use of the transformation to the point location problem in En. Using the transformation beween problems for estimating the lower bound of time complexity.
Fundamental techniques of creating effective algorithms: plane sweeping method, divide and conquer method, prune and search method, randomised algorithms.
Point location problem. Determining mutual position of a point and a simple polygon. Determining position of a point in a planar map. Identification of points that fall into a given rectangular area. Applications.
Convex hull. Algorithms for determining the convex hull in the two-dimensional space.
Convex hull in more-dimensional spaces. Convex hull in E3. Applications of convex hull.
The problems of distance and proximity. Finding the pair of closest points in E2 and in En. Element uniqueness problem.
Voronoi diagram. Constructing the Voronoi diagram. Proximity problems solved by the Voronoi diagram.
Triangulation. Delaunay triangulation and its properties. A randomised algorithm for computing the Delaunay triangulation. Triangulation of a simple polygon.
Intersections. Finding the intersections of a set of line segments in E2. Intersection of simple polygons.
Binary space partitioning. BSP trees. Applications.
Visibility relation. Visibility graph. Computing visibility graph for planar problems. Applications.
On the application of the problems discussed in the subject: Planning the motion of a mobile robot.
Exercises:
During the exercises, the students construct algorithms that solve given problems. They vindicate the algorithms in the discussion, and evaluate their time and space complexities.
Computer labs:
For one selected problem, the students will also carry the detailed implementation.
The complexity of a problem and the complexity of an algorithm. The complexity in the worst case, expected complexity. Models of computation. RAM, algebraic decision tree.
Estimating the lower bound of the worst case time complexity by making use of the transformation to the point location problem in En. Using the transformation beween problems for estimating the lower bound of time complexity.
Fundamental techniques of creating effective algorithms: plane sweeping method, divide and conquer method, prune and search method, randomised algorithms.
Point location problem. Determining mutual position of a point and a simple polygon. Determining position of a point in a planar map. Identification of points that fall into a given rectangular area. Applications.
Convex hull. Algorithms for determining the convex hull in the two-dimensional space.
Convex hull in more-dimensional spaces. Convex hull in E3. Applications of convex hull.
The problems of distance and proximity. Finding the pair of closest points in E2 and in En. Element uniqueness problem.
Voronoi diagram. Constructing the Voronoi diagram. Proximity problems solved by the Voronoi diagram.
Triangulation. Delaunay triangulation and its properties. A randomised algorithm for computing the Delaunay triangulation. Triangulation of a simple polygon.
Intersections. Finding the intersections of a set of line segments in E2. Intersection of simple polygons.
Binary space partitioning. BSP trees. Applications.
Visibility relation. Visibility graph. Computing visibility graph for planar problems. Applications.
On the application of the problems discussed in the subject: Planning the motion of a mobile robot.
Exercises:
During the exercises, the students construct algorithms that solve given problems. They vindicate the algorithms in the discussion, and evaluate their time and space complexities.
Computer labs:
For one selected problem, the students will also carry the detailed implementation.