A new generalized Voronoi diagram in the plane

In this thesis, a new generalized Voronoi diagram in the plane, called a bounded Voronoi diagram, is defined. This generalization is one of the natural extensions of the previously existing Voronoi diagrams in the plane. Three important cases of bounded Voronoi diagrams are discussed. They are: (1) The bounded Voronoi diagram for a monotone chain. (2) The bounded Voronoi diagram for a simple polygon. (3) The bounded Voronoi diagram for a set of non-crossing line segments. Algorithms for constructing these bounded Voronoi diagrams are presented. All of them are optimal. Bounded Voronoi diagrams are powerful tools which help to efficiently solve many geometric problems.