Papadopoulou, Evanthia Dey, Sandeep Kumar 2015-06-16 Voronoi diagrams and their numerous variants are well-established objects in computational geometry. They have proven to be extremely useful to tackle geometric problems in various domains such as VLSI CAD, Computer Graphics, Pattern Recognition, Information Retrieval, etc. In this dissertation, we study generalized Voronoi diagram of line segments as motivated by applications in VLSI Computer Aided Design. Our work has three directions: algorithms, implementation, and applications of the line-segment Voronoi diagrams. Our results are as follows: (1) Algorithms for the farthest Voronoi diagram of line segments in the Lp metric, 1 ≤ p ≤ ∞. Our main interest is the L2 (Euclidean) and the L∞ metric. We first introduce the farthest line-segment hull and its Gaussian map to characterize the regions of the farthest line-segment Voronoi diagram at infinity. We then adapt well-known techniques for the construction of a convex hull to compute the farthest line-segment hull, and therefore, the farthest segment Voronoi diagram. Our approach unifies techniques to compute farthest Voronoi diagrams for points and line segments. (2) The implementation of the L∞ Voronoi diagram of line segments in the Computational Geometry Algorithms Library (CGAL). Our software (approximately 17K lines of C++ code) is built on top of the existing CGAL package on the L2 (Euclidean) Voronoi diagram of line segments. It is accepted and integrated in the upcoming version of the library CGAL-4.7 and will be released in september 2015. We performed the implementation in the L∞ metric because we target applications in VLSI design, where shapes are predominantly rectilinear, and the L∞ segment Voronoi diagram is computationally simpler. (3) The application of our Voronoi software to tackle proximity-related problems in VLSI pattern analysis. In particular, we use the Voronoi diagram to identify critical locations in patterns of VLSI layout, which can be faulty during the printing process of a VLSI chip. We present experiments involving layout pieces that were provided by IBM Research, Zurich. Our Voronoi-based method was able to find all problematic locations in the provided layout pieces, very fast, and without any manual intervention. application/pdf https://susi.usi.ch/global/documents/318605 https://n2t.net/ark:/12658/srd1318605 https://susi.usi.ch/documents/318605/files/2015INFO007.pdf eng info:eu-repo/semantics/altIdentifier/urn/urn:nbn:ch:rero-006-114276 info:eu-repo/semantics/altIdentifier/ark/12658/srd1318605 info:eu-repo/semantics/openAccess License undefined Voronoi diagram Max-norm Combinatorial bounds Farthest hull CGAL Implementation VLSI Pattern analysis info:eu-repo/classification/udc/004 Voronoi diagrams in the max-norm : algorithms, implementation, and applications http://purl.org/coar/resource_type/c_db06