We consider the Voronoi diagram of lines in ℝ³ under the Euclidean metric, and give a full classification of its structure in the base case of four lines in general position. We first show that the number of vertices in the Voronoi diagram of four lines in general position is always even, between 0 and 8, and all such numbers can be realized. We identify a key structure for the diagram formation, called a twist, which is a pair of consecutive intersections among trisector branches; only two types of twists are possible, so-called full and partial twists. A full twist is a purely local structure, which can be inserted or removed without affecting the rest of the diagram. Assuming no full twists, the nearest and the farthest Voronoi diagrams of four lines, each have 15 distinct topologies, which are in one-to-one correspondence; the two-dimensional faces are all unbounded, and the total number of vertices is at most six. The unbounded features of the farthest diagram, encoded in a two-dimensional spherical map, are also in one-to-one correspondence. The identified topologies are all realizable. Any Voronoi diagram of four lines in general position in ℝ³ can be obtained from one of these topologies by inserting full twists; each twist induces a bounded face of exactly two vertices in both the nearest and farthest diagrams. We obtain the classification by an exhaustive search algorithm using some new structural and combinatorial observations of line Voronoi diagrams.

Abstract Voronoi diagrams are defined in terms of a given system of planar bisecting curves satisfying some simple combinatorial properties. They offer a unifying framework for a wide range of concrete Voronoi instances on generalized sites and metrics. In this paper, we formulate higher-order abstract color Voronoi diagrams of a set S of n colored abstract sites, simultaneously considering all concrete instances under their umbrella. We prove that the number of vertices in the order-k abstract color Voronoi diagram is at most 4k(n-k)-2n, and present an iterative construction algorithm. The bound directly applies to a family of m disjoint simple polygons of total complexity n. For simple polygons the bound can further improve to O(min{k(n-k),(m-k)²n}). A critical ingredient of our proof is a combinatorial analysis on circular sequences of color permutations derived from the unbounded edges of these diagrams that is interesting in its own right.

Given a set $S$ of $n$ colored sites, each $s\in S$ associated with a distance-to-site function $δ_s \colon \mathbb{R}^2 \to \mathbb{R}$, we consider two distance-to-color functions for each color: one takes the minimum of $δ_s$ for sites $s\in S$ in that color and the other takes the maximum. These two sets of distance functions induce two families of higher-order Voronoi diagrams for colors in the plane, namely, the minimal and maximal order-$k$ color Voronoi diagrams, which include various well-studied Voronoi diagrams as special cases. In this paper, we derive an exact upper bound $4k(n-k)-2n$ on the total number of vertices in both the minimal and maximal order-$k$ color diagrams for a wide class of distance functions $δ_s$ that satisfy certain conditions, including the case of point sites $S$ under convex distance functions and the $L_p$ metric for any $1\leq p \leq\infty$. For the $L_1$ (or, $L_\infty$) metric, and other convex polygonal metrics, we show that the order-$k$ minimal diagram of point sites has $O(\min\{k(n-k), (n-k)^2\})$ complexity, while its maximal counterpart has $O(\min\{k(n-k), k^2\})$ complexity. To obtain these combinatorial results, we extend the Clarkson--Shor framework to colored objects, and demonstrate its application to several fundamental geometric structures, including higher-order color Voronoi diagrams, colored $j$-facets, and levels in the arrangements of piecewise linear/algebraic curves/surfaces. We also present an iterative approach to compute higher-order color Voronoi diagrams.

Abstract The farthest-color Voronoi diagram (FCVD) is defined on a set of n points in the plane, where each point is labeled with one of m colors. The colored points constitute a family $$\mathcal {P}$$ P of m clusters (sets) of points in the plane whose farthest-site Voronoi diagram is the FCVD. The diagram finds applications in problems related to facility location, shape matching, data imprecision, and others. In this paper we present structural properties of the FCVD, refine its combinatorial complexity bounds, and present efficient algorithms for its construction. We show that the complexity of the diagram is $$O(n\alpha (m)+\textit{str}(\mathcal {P}))$$ O ( n α ( m ) + str ( P ) ) , where $$\textit{str}(\mathcal {P})$$ str ( P ) is a parameter reflecting the number of straddles between pairs of clusters, which is $$O(m(n-m))$$ O ( m ( n - m ) ) . The bound reduces to $$O(n+ \textit{str}(\mathcal {P}))$$ O ( n + str ( P ) ) if the clusters are pairwise non-crossing . We also present a lower bound, establishing that the complexity of the FCVD can be $$\Omega (n+m^2)$$ Ω ( n + m 2 ) , even if the clusters have pairwise disjoint convex hulls. Our algorithm runs in $$O((n+\textit{str}(\mathcal {P}))\log ^3 n)$$ O ( ( n + str ( P ) ) log 3 n ) -time, and in certain special cases in $$O(n\log n)$$ O ( n log n ) time.

Abstract We study the behavior at infinity of the farthest and the higher-order Voronoi diagram of n line segments or lines in a d-dimensional Euclidean space. The unbounded parts of these diagrams can be encoded by a Gaussian map on the sphere of directions $$\mathbb {S}^{d-1}$$ S d - 1 . We show that the combinatorial complexity of the Gaussian map for the order-k Voronoi diagram of n line segments and lines is $$O(\min \{k,n-k\}n^{d-1})$$ O ( min { k , n - k } n d - 1 ) , which is tight for $$n-k=O(1)$$ n - k = O ( 1 ) . This exactly reflects the combinatorial complexity of the unbounded features of these diagrams. All the d-dimensional cells of the farthest Voronoi diagram are unbounded, its $$(d-1)$$ ( d - 1 ) -skeleton is connected, and it does not have tunnels. A d-cell of the Voronoi diagram is called a tunnel if the set of its unbounded directions, represented as points on its Gaussian map, is not connected. In a three-dimensional space, the farthest Voronoi diagram of $$n \ge 2$$ n ≥ 2 lines in general position has exactly $$n(n-1)$$ n ( n - 1 ) three-dimensional cells. The Gaussian map of the farthest Voronoi diagram of line segments and lines can be constructed in $$O(n^{d-1} \alpha (n))$$ O ( n d - 1 α ( n ) ) time, for $$d\ge 4$$ d ≥ 4 , while if $$d=3$$ d = 3 , the time drops to worst-case optimal $$\Theta (n^2)$$ Θ ( n 2 ) . We extend the obtained results to bounded polyhedra and clusters of points as sites.

Any system of bisectors (in the sense of abstract Voronoi diagrams) defines an arrangement of simple curves in the plane. We define Voronoi-like graphs on such an arrangement, which are graphs whose vertices are locally Voronoi. A vertex $v$ is called locally Voronoi, if $v$ and its incident edges appear in the Voronoi diagram of three sites. In a so-called admissible bisector system, where Voronoi regions are connected and cover the plane, we prove that any Voronoi-like graph is indeed an abstract Voronoi diagram. The result can be seen as an abstract dual version of Delaunay's theorem on (locally) empty circles. Further, we define Voronoi-like cycles in an admissible bisector system, and show that the Voronoi-like graph induced by such a cycle $C$ is a unique tree (or a forest, if $C$ is unbounded). In the special case where $C$ is the boundary of an abstract Voronoi region, the induced Voronoi-like graph can be computed in expected linear time following the technique of [Junginger and Papadopoulou SOCG'18]. Otherwise, within the same time, the algorithm constructs the Voronoi-like graph of a cycle $C'$ on the same set (or subset) of sites, which may equal $C$ or be enclosed by $C$. Overall, the technique computes abstract Voronoi (or Voronoi-like) trees and forests in linear expected time, given the order of their leaves along a Voronoi-like cycle. We show a direct application in updating a constraint Delaunay triangulation in linear expected time, after the insertion of a new segment constraint, simplifying upon the result of [Shewchuk and Brown CGTA 2015].

Abstract Updating an abstract Voronoi diagram in linear time, after deletion of one site, has been an open problem in a long time; similarly, for any concrete Voronoi diagram of generalized (non-point) sites. In this paper we present a simple, expected linear-time algorithm to update an abstract Voronoi diagram after deletion of one site. To achieve this result, we use the concept of a Voronoi-like diagram, a relaxed Voronoi structure of independent interest. Voronoi-like diagrams serve as intermediate structures, which are considerably simpler to compute, thus, making an expected linear-time construction possible. We formalize the concept and prove that it is robust under insertion, therefore, enabling its use in incremental constructions. The time-complexity analysis introduces a variant to backwards analysis, which is applicable to order-dependent structures. We further extend the technique to compute in expected linear time: the order- $$(k\,{+}\,1)$$ ( k + 1 ) subdivision within an order-k Voronoi region, and the farthest abstract Voronoi diagram, after the order of its regions at infinity is known.

Given a set A of n points in ℝ^d with weight function w: A→ℝ_{> 0}, the Fermat distance function is φ(x): = ∑_{a∈A}w(a)‖x-a‖. A classic problem in facility location dating back to 1643, is to find the Fermat point x*, the point that minimizes the function φ. We consider the problem of computing a point x̃* that is an ε-approximation of x* in the sense that ‖x̃*-x*‖<ε. The algorithmic literature has so far used a different notion based on ε-approximation of the value φ(x*). We devise a certified subdivision algorithm for computing x̃*, enhanced by Newton operator techniques. We also revisit the classic Weiszfeld-Kuhn iteration scheme for x*, turning it into an ε-approximate Fermat point algorithm. Our second problem is the certified construction of ε-isotopic approximations of n-ellipses. These are the level sets φ^{-1}(r) for r > φ(x*) and d = 2. Finally, all our planar (d = 2) algorithms are implemented in order to experimentally evaluate them, using both synthetic as well as real world datasets. These experiments show the practicality of our techniques.

Voronoi diagrams induced by distance functions whose unit balls are convex polyhedra are piecewise-linear structures. Nevertheless, analyzing their combinatorial and algorithmic properties in dimensions three and higher is an intriguing problem. The situation turns easier when the farthest-site variants of such Voronoi diagrams are considered, where each site gets assigned the region of all points in space farthest from (rather than closest to) it. We give asymptotically tight upper and lower worst-case bounds on the combinatorial size of farthest-site Voronoi diagrams for convex polyhedral distance functions in general dimensions, and propose an optimal construction algorithm. Our approach is uniform in the sense that (1) it can be extended from point sites to sites that are convex polyhedra, (2) it covers the case where the distance function is additively and/or multiplicatively weighted, and (3) it allows an anisotropic scenario where each site gets allotted its particular convex distance polytope.

We study the behavior at infinity of the farthest and the higher-order Voronoi diagram of n line segments or lines in a d-dimensional Euclidean space. The unbounded parts of these diagrams can be encoded by a Gaussian map on the sphere of directions S^(d-1). We show that the combinatorial complexity of the Gaussian map for the order-k Voronoi diagram of n line segments or lines is O(min{k,n-k} n^(d-1)), which is tight for n-k = O(1). All the d-dimensional cells of the farthest Voronoi diagram are unbounded, its (d-1)-skeleton is connected, and it does not have tunnels. A d-cell of the Voronoi diagram is called a tunnel if the set of its unbounded directions, represented as points on its Gaussian map, is not connected. In a three-dimensional space, the farthest Voronoi diagram of lines has exactly n^2-n three-dimensional cells, when n >= 2. The Gaussian map of the farthest Voronoi diagram of line segments or lines can be constructed in O(n^(d-1) alpha(n)) time, while if d=3, the time drops to worst-case optimal O(n^2).

Updating an abstract Voronoi diagram in linear time, after deletion of one site, has been an open problem for a long time. Similarly for various concrete Voronoi diagrams of generalized sites, other than points. In this paper we present a simple, expected linear-time algorithm to update an abstract Voronoi diagram after deletion. We introduce the concept of a Voronoi-like diagram, a relaxed version of a Voronoi construct that has a structure similar to an abstract Voronoi diagram, without however being one. Voronoi-like diagrams serve as intermediate structures, which are considerably simpler to compute, thus, making an expected linear-time construction possible. We formalize the concept and prove that it is robust under an insertion operation, thus, enabling its use in incremental constructions.

Abstract Let X = {f1, …, fn} be a set of scalar functions of the form fi : ℝ2 → ℝ which satisfy some natural properties. We describe a subdivision algorithm for computing a clustered ε‐isotopic approximation of the minimization diagram of X. By exploiting soft predicates and clustering of Voronoi vertices, our algorithm is the first that can handle arbitrary degeneracies in X, and allow scalar functions which are piecewise smooth, and not necessarily semi‐algebraic. We apply these ideas to the computation of anisotropic Voronoi diagram of polygonal sets; this is a natural generalization of anisotropic Voronoi diagrams of point sites, which extends multiplicatively weighted Voronoi diagrams. We implement a prototype of our anisotropic algorithm and provide experimental results.

We address the problem of computing critical area for open faults (opens) in a circuit layout in the presence of multilayer loops and redundant interconnects. The extraction of critical area is the main computational bottleneck in predicting the yield loss of a very large scale integrated design due to random manufacturing defects. We first model the problem as a geometric graph problem and we solve it efficiently by exploiting its geometric nature. To model open faults, we formulate a new geometric version of the classic min-cut problem in graphs, termed the geometric min-cut problem. Then the critical area extraction problem gets reduced to the construction of a generalized Voronoi diagram for open faults, based on concepts of higher order Voronoi diagrams. The approach expands the Voronoi critical area computation paradigm with the ability to accurately compute critical area for missing material defects even in the presence of loops and redundant interconnects spanning over multiple layers. The generalized Voronoi diagrams used in the solution are combinatorial structures of independent interest.

We address the problem of computing critical area for missing material defects in a circuit layout. The extraction of critical area is the main computational problem in very large scale integration yield prediction. Missing material defects cause open circuits and are classified into breaks and via blocks. Our approach is based on the L/sub /spl infin// medial axis of polygons and the weighted L/sub /spl infin// Voronoi diagram of segments. We also introduce the min-max Voronoi diagram of rectangles, a combinatorial structure of independent interest. The critical area problem for breaks and via blocks is reduced to variations of weighted L/sub /spl infin// Voronoi diagram of segments. Plane sweep algorithms to compute the appropriate Voronoi diagrams for each case are presented. As a result, the critical area for breaks and via blocks on a single layer can be computed accurately in one pass of the layout. The time complexity is O(n log n) in the case of breaks and O((n+K)log n) in the case of via blocks, where n is the size of the input and K is upper-bounded by the number of interacting vias (in practice K is small). The critical area computation assumes square defects and reflects all possible defect sizes following the D(r)=r/sub 0//sup 2//r/sup 3/ defect size distribution. The method is presented for rectilinear layouts.

We address the problem of computing critical area for missing material defects in a circuit layout.The extraction of critical area is the main computational problem in VLSI yield prediction. Missing material defects cause open circuits and are classi ed into breaks and via-blocks.Our approach is based on the L1 medial axis of polygons and the weighted L1 Voronoi diagram of segments.The critical area problem for both breaks and via-blocks is reduced to a weighted L1 Voronoi diagram of segments.This reduction results in a plane sweep algorithm to compute critical area in one pass.The time complexity i s O(n log n) in the case of breaks and O(n log n + K) in the case of via-blocks, where n is the size of the input and K is bounded by the number of interacting vias (in practice K is small).The critical area computation assumes square defects and re ects all possible defect sizes following the D(r) = r 2 0 =r 3 defect size distribution.The method is presented for rectilinear layouts.

In this paper, we present a new approach for computing the critical area for shorts in a circuit layout. The critical area calculation is the main computational problem in very large scale integration yield prediction. The method is based on the concept of Voronoi diagrams and computes the critical area for shorts (for all possible defect radii, assuming square defects) accurately in O(n log n) time, where n is the size of the input. The method is presented for rectilinear layouts and layouts containing edges of slope /spl plusmn/1. As a byproduct, we briefly sketch how to speed up the grid method of Wagner and Koren [1995].

In this paper we present a new approach for computing the critical area for shorts in a circuit layout. The critical area calculation is the main computational problem in VLSI yield prediction. The method is based on the concept of Voronoi diagrams and computes the critical area for shorts (for all possible defect radii, assuming square defects) accurately in O(n log n) time, where n is the size of the input. The method is presented for rectilinear layouts but it is extendible to general layouts. As a byproduct we briefly sketch how to speed up the grid method of Wagner and Koren [16].

Pemmsim to make digil:lldl:[r(i topics td'Jll (Jr patl ollhis m21trlal I'or pcrsmull or classroom IIs< ,s granlc(l L,ilhiml ILCprovided 111:11 Ilw c(>p,cs 'Ire Il[>t!)l:ldL> or dislrihllt~>d till prL)til Of LXIIII 111 C1L,i:ll fi[i\l:lll!:lgC.!ht.L,~)p\,- rigJlt notic.c.(hc title ot'[he pulll Icall(l[l (l[l[i ils dole appear.and nolicc is given LIIA copyright is 11~pcmllsslon (11'llw ;\C1l.[m.'10 copy o[hcnviw, to republish.Iu pos[ on scmvrs or 10 rcdlstrilwlc 10 Iisls.rcqutl-esspccitic permission wvllor lit (Compurm]onol (;comelq, 97 N'icc I'rmlcc