Given a simple polygon P with n vertices, we consider the problem of constructing a data structure for visibility queries: for any query point q ∈ P, compute the visibility polygon of q in P. To obtain O(log n + k) query time, where k is the size of the visibility polygon of q, the previous best result requires O(n³) space. In this paper, we propose a new data structure that uses O(n^{2+ε}) space, for any ε > 0, while achieving the same query time. If only O(n²) space is available, the best known result provides O(log² n + k) query time. We improve this to O(log n log log n + k) time. When restricted to o(n²) space, the only previously known approach, aside from the O(n)-time algorithm that computes the visibility polygon without preprocessing, is an O(n)-space data structure that supports O(k log n)-time queries. We construct a data structure using O(n log n) space that answers visibility queries in O(n^{1/2+ε} + k) time. In addition, for the special case in which q lies on the boundary of P, we build a data structure of O(n log n) space supporting O(log² n + k) query time; alternatively, we achieve O(log n + k) query time using O(n^{1+ε}) space. To achieve our results, we propose a new method for decomposing simple polygons, which may be of independent interest.

We develop a technique to design efficiently computable estimators for sparse linear regression in the simultaneous presence of two adversaries: oblivious and adaptive. Consider the model $y^*=X^*\beta^*+ \eta$ where $X^*$ is an $n\times d$ random design matrix, $\beta^*\in \mathbb{R}^d$ is a $k$-sparse vector, and the noise $\eta$ is independent of $X^*$ and chosen by the \emph{oblivious adversary}. Apart from the independence of $X^*$, we only require a small fraction entries of $\eta$ to have magnitude at most $1$. The \emph{adaptive adversary} is allowed to arbitrarily corrupt an $\varepsilon$-fraction of the samples $(X_1^*, y_1^*),\ldots, (X_n^*, y_n^*)$. Given the $\varepsilon$-corrupted samples $(X_1, y_1),\ldots, (X_n, y_n)$, the goal is to estimate $\beta^*$. We assume that the rows of $X^*$ are iid samples from some $d$-dimensional distribution $\mathcal{D}$ with zero mean and (unknown) covariance matrix $\Sigma$ with bounded condition number. We design several robust algorithms that outperform the state of the art even in the special case of Gaussian noise $\eta \sim N(0,1)^n$. In particular, we provide a polynomial-time algorithm that with high probability recovers $\beta^*$ up to error $O(\sqrt{\varepsilon})$ as long as $n \ge \tilde{O}(k^2/\varepsilon)$, only assuming some bounds on the third and the fourth moments of $\mathcal{D}$. In addition, prior to this work, even in the special case of Gaussian design $\mathcal{D} = N(0,\Sigma)$ and noise $\eta \sim N(0,1)$, no polynomial time algorithm was known to achieve error $o(\sqrt{\varepsilon})$ in the sparse setting $n < d^2$. We show that under some assumptions on the fourth and the eighth moments of $\mathcal{D}$, there is a polynomial-time algorithm that achieves error $o(\sqrt{\varepsilon})$ as long as $n \ge \tilde{O}(k^4 / \varepsilon^3)$. For Gaussian distribution $\mathcal{D} = N(0,\Sigma)$, this algorithm achieves error $O(\varepsilon^{3/4})$. Moreover, our algorithm achieves error $o(\sqrt{\varepsilon})$ for all log-concave distributions if $\varepsilon \le 1/\text{polylog(d)}$. Our algorithms are based on the filtering of the covariates that uses sum-of-squares relaxations, and weighted Huber loss minimization with $\ell_1$ regularizer. We provide a novel analysis of weighted penalized Huber loss that is suitable for heavy-tailed designs in the presence of two adversaries. Furthermore, we complement our algorithmic results with Statistical Query lower bounds, providing evidence that our estimators are likely to have nearly optimal sample complexity.

We develop the first pure node-differentially-private algorithms for learning stochastic block models and for graphon estimation with polynomial running time for any constant number of blocks. The statistical utility guarantees match those of the previous best information-theoretic (exponential-time) node-private mechanisms for these problems. The algorithm is based on an exponential mech- anism for a score function defined in terms of a sum-of-squares relaxation whose level depends on the number of blocks. The key ingredients of our results are (1) a characterization of the distance between the block graphons in terms of a quadratic optimization over the polytope of doubly stochastic matrices, (2) a general sum-of-squares convergence result for polynomial op- timization over arbitrary polytopes, and (3) a general approach to perform Lipschitz extensions of score functions as part of the sum-of-squares algorithmic paradigm.

Given n elements, an integer k ≤ n/2 and a parameter ε ≥ 1/n, we study the problem of selecting an element with rank in (k-nε, k+nε] using unreliable comparisons where the outcome of each comparison is incorrect independently with a constant error probability, and multiple comparisons between the same pair of elements are independent. In this fault model, the fundamental problems of finding the minimum, selecting the k-th smallest element and sorting have been shown to require Θ(n log 1/Q), Θ(n log k/Q) and Θ(n log n/Q) comparisons, respectively, to achieve success probability 1-Q [Uriel Feige et al., 1994]. Considering the increasing complexity of modern computing, it is of great interest to develop approximation algorithms that enable a trade-off between the solution quality and the number of comparisons. In particular, approximation algorithms would even be able to attain a sublinear number of comparisons. Very recently, Leucci and Liu [Stefano Leucci and Chih-Hung Liu, 2022] proved that the approximate minimum selection problem, which covers the case that k ≤ nε, requires expected Θ(ε^{-1} log 1/Q) comparisons, but the general case, i.e., for nε < k ≤ n/2, is still open. We develop a randomized algorithm that performs expected O(k/n ε^{-2} log 1/Q) comparisons to achieve success probability at least 1-Q. For k = n ε, the number of comparisons is O(ε^{-1} log 1/Q), matching Leucci and Liu’s result [Stefano Leucci and Chih-Hung Liu, 2022], whereas for k = n/2 (i.e., approximating the median), the number of comparisons is O(ε^{-2} log 1/Q). We also prove that even in the absence of comparison faults, any randomized algorithm with success probability at least 1-Q performs expected Ω(min{n, k/n ε^{-2} log 1/Q}) comparisons. As long as n is large enough, i.e., when n = Ω(k/n ε^{-2} log 1/Q), our lower bound demonstrates the optimality of our algorithm, which covers the possible range of attaining a sublinear number of comparisons. Surprisingly, for constant Q, our algorithm performs expected O(k/n ε^{-2}) comparisons, matching the best possible approximation algorithm in the absence of computation faults. In contrast, for the exact selection problem, the expected number of comparisons is Θ(n log k) with faults versus Θ(n) without faults. Our results also indicate a clear distinction between approximating the minimum and approximating the k-th smallest element, which holds even for the high probability guarantee, e.g., if k = n/2, Q = 1/n and ε = n^{-α} for α ∈ (0, 1/2), the asymptotic difference is almost quadratic, i.e., Θ̃(n^α) versus Θ̃(n^{2α}).

We develop the first fast spectral algorithm to decompose a random third-order tensor over of rank up to $$O(d^{3/2}/polylog(d))$$. Our algorithm only involves simple linear algebra operations and can recover all components in time $$O(d^{6.05})$$ under the current matrix multiplication time. Prior to this work, comparable guarantees could only be achieved via sum-of-squares [Ma, Shi, Steurer 2016]. In contrast, fast algorithms [Hopkins, Schramm, Shi, Steurer 2016] could only decompose tensors of rank at most $$O(d^{4/3}/polylog(d))$$. Our algorithmic result rests on two key ingredients. A clean lifting of the third-order tensor to a sixth-order tensor, which can be expressed in the language of tensor networks. A careful decomposition of the tensor network into a sequence of rectangular matrix multiplications, which allows us to have a fast implementation of the algorithm.

Abstract We consider the approximate minimum selection problem in presence of independent random comparison faults. This problem asks to select one of the smallest k elements in a linearly-ordered collection of n elements by only performing unreliable pairwise comparisons: whenever two elements are compared, there is a small probability that the wrong comparison outcome is observed. We design a randomized algorithm that solves this problem with a success probability of at least $$1-q$$ 1 - q for $$q \in (0, \frac{n-k}{n})$$ q ∈ ( 0 , n - k n ) and any $$k \in [1, n-1]$$ k ∈ [ 1 , n - 1 ] using $$O\big ( \frac{n}{k} \big \lceil \log \frac{1}{q} \big \rceil \big )$$ O ( n k ⌈ log 1 q ⌉ ) comparisons in expectation (if $$k \ge n$$ k ≥ n or $$q \ge \frac{n-k}{n}$$ q ≥ n - k n the problem becomes trivial). Then, we prove that the expected number of comparisons needed by any algorithm that succeeds with probability at least $$1-q$$ 1 - q must be $${\varOmega }(\frac{n}{k}\log \frac{1}{q})$$ Ω ( n k log 1 q ) whenever q is bounded away from $$\frac{n-k}{n}$$ n - k n , thus implying that the expected number of comparisons performed by our algorithm is asymptotically optimal in this range. Moreover, we show that the approximate minimum selection problem can be solved using $$O( (\frac{n}{k} + \log \log \frac{1}{q}) \log \frac{1}{q})$$ O ( ( n k + log log 1 q ) log 1 q ) comparisons in the worst case, which is optimal when q is bounded away from $$\frac{n-k}{n}$$ n - k n and $$k = O\big ( \frac{n}{\log \log \frac{1}{q}}\big )$$ k = O ( n log log 1 q ) .

We study the $k$ nearest neighbors problem in the plane for general, convex, pairwise disjoint sites of constant description complexity such as line segments, disks, and quadrilaterals under a general family of distance functions including the $L_p$ norms and additively weighted Euclidean distances. We compose a static data structure for this general setting with nearly optimal $O(n\log\log n)$ space, optimal $O(\log n+k)$ query time, and optimal expected $O(n\log n)$ preprocessing time. We also devise a dynamic data structure (that allows insertions and deletions of sites) with $O(n\log n)$ space, $O(\log^2n+k\log n)$ query time, and expected amortized $O(\log^2 n)$ insertion time and $O(\log^4n)$ deletion time, matching the best known time complexities for point sites in the Euclidean metric and improving many applications such as dynamic minimum spanning trees in a general planar metric and dynamic connectivity in disk intersection graphs. Our results, to some extent, indicate that for the $k$ nearest neighbors problem, general distance functions may share the same time complexities with point sites in the Euclidean metric. To achieve this progress, we design vertical shallow cuttings of linear size for general distance functions. Vertical shallow cuttings are a key technique to tackle the $k$ nearest neighbors problem for point sites in the Euclidean metric, while existing generalizations to general distance functions are either not vertical or not of linear size. Our innovation is a new random sampling technique for the analysis of geometric structures, and since this technique provides a new way to develop geometric algorithms, we believe it is of independent interest.

We develop machinery to design efficiently computable and \emph{consistent} estimators, achieving estimation error approaching zero as the number of observations grows, when facing an oblivious adversary that may corrupt responses in all but an $\alpha$ fraction of the samples.As concrete examples, we investigate two problems: sparse regression and principal component analysis (PCA).For sparse regression, we achieve consistency for optimal sample size $n\gtrsim (k\log d)/\alpha^2$ and optimal error rate $O(\sqrt{(k\log d)/(n\cdot \alpha^2)})$where $n$ is the number of observations, $d$ is the number of dimensions and $k$ is the sparsity of the parameter vector, allowing the fraction of inliers to be inverse-polynomial in the number of samples.Prior to this work, no estimator was known to be consistent when the fraction of inliers $\alpha$ is $o(1/\log \log n)$, even for (non-spherical) Gaussian design matrices.Results holding under weak design assumptions and in the presence of such general noise have only been shown in dense setting (i.e., general linear regression) very recently by d'Orsi et al.~\cite{ICML-linear-regression}.In the context of PCA, we attain optimal error guarantees under broad spikiness assumptions on the parameter matrix (usually used in matrix completion). Previous works could obtain non-trivial guarantees only under the assumptions that the measurement noise corresponding to the inliers is polynomially small in $n$ (e.g., Gaussian with variance $1/n^2$).To devise our estimators, we equip the Huber loss with non-smooth regularizers such as the $\ell_1$ norm or the nuclear norm, and extend d'Orsi et al.'s approach~\cite{ICML-linear-regression} in a novel way to analyze the loss function.Our machinery appears to be easily applicable to a wide range of estimation problems.We complement these algorithmic results with statistical lower bounds showing that the fraction of inliers that our PCA estimator can deal with is optimal up to a constant factor.

We study the k nearest neighbors problem in the plane for general, convex, pairwise disjoint sites of constant description complexity such as line segments, disks, and quadrilaterals and with respect to a general family of distance functions including the Lp-norms and additively weighted Euclidean distances. For point sites in the Euclidean metric, after four decades of effort, an optimal data structure has recently been developed with O(n) space, O(log n + k) query time, and O(n log n) preprocessing time [1, 17]. We develop a static data structure for the general setting with nearly optimal O(n log log n) space, the optimal O(log n + k) query time, and expected O(n polylog n) preprocessing time. The O(n log log n) space approaches the linear space, whose achievability is still unknown with the optimal query time, and improves the so far best O(n(log2 n)(log log n)2) space of Bohler et al.'s work [12]. Our dynamic version (that allows insertions and deletions of sites) also reduces the space of Kaplan et al.'s work [29] from O(n log3 n) to O(n log n) while keeping O(log2 n + k) query time and O(polylog n) update time, thus improving many applications such as dynamic bichromatic closest pair and dynamic minimum spanning tree in general planar metric, and shortest path tree and dynamic connectivity in disk intersection graphs. To obtain these progresses, we devise shallow cuttings of linear size for general distance functions. Shallow cuttings are a key technique to deal with the k nearest neighbors problem for point sites in the Euclidean metric. Agarwal et al. [4] already designed linear-size shallow cuttings for general distance functions, but their shallow cuttings could not be applied to the k nearest neighbors problem. Recently, Kaplan et al. [29] constructed shallow cuttings that are feasible for the k nearest neighbors problem, while the size of their shallow cuttings has an extra double logarithmic factor. Our innovation is a new random sampling technique for the analysis of geometric structures. While our shallow cuttings seem, to some extent, merely a simple transformation of Agarwal et al.'s [4], the analysis requires our new technique to attain the linear size. Since our new technique provides a new way to develop and analyze geometric algorithms, we believe it is of independent interest.

The geodesic Voronoi diagram of m point sites inside a simple polygon of n vertices is a subdivision of the polygon into m cells, one to each site, such that all points in a cell share the same nearest site under the geodesic distance. The best known lower bound for the construction time is $$\varOmega (n+m\log m)$$ Ω(n+mlogm), and a matching upper bound is a long-standing open question. The state-of-the-art construction algorithms achieve $$O( (n+m) \log (n+m) )$$ O((n+m)log(n+m)) and $$O(n+m\log m\log ^2n)$$ O(n+mlogmlog2n) time, which are optimal for $$m=\varOmega (n)$$ m=Ω(n) and $$m=O(\frac{n}{\log ^3n})$$ m=O(nlog3n), respectively. In this paper, we give a construction algorithm with $$O( n + m ( \log m+ \log ^2 n ) )$$ O(n+m(logm+log2n)) time, and it is nearly optimal in the sense that if a single Voronoi vertex can be computed in $$O(\log n)$$ O(logn) time, then the construction time will become the optimal $$O(n+m\log m)$$ O(n+mlogm). In other words, we reduce the problem of constructing the diagram in the optimal time to the problem of computing a single Voronoi vertex in $$O(\log n)$$ O(logn) time.

We study the problem of designing a dictionary data structure that is resilient to memory corruptions. Our error model is a variation of the faulty RAM model in which, except for constant amount of definitely reliable memory, each memory word is randomly unreliable with a probability p < 1/2, and the locations of the unreliable words are unknown to the algorithm. An adversary observes the whole memory and can, at any time, arbitrarily corrupt (i.e., modify) the contents of one or more unreliable words. Our dictionary has capacity n, stores N

We consider the problem of sorting $n$ elements in the case of \emph{persistent} comparison errors. In this model (Braverman and Mossel, SODA'08), each comparison between two elements can be wrong with some fixed (small) probability $p$, and \emph{comparisons cannot be repeated}. Sorting perfectly in this model is impossible, and the objective is to minimize the \emph{dislocation} of each element in the output sequence, that is, the difference between its true rank and its position. Existing lower bounds for this problem show that no algorithm can guarantee, with high probability, \emph{maximum dislocation} and \emph{total dislocation} better than $Ω(\log n)$ and $Ω(n)$, respectively, regardless of its running time. In this paper, we present the first \emph{$O(n\log n)$-time} sorting algorithm that guarantees both \emph{$O(\log n)$ maximum dislocation} and \emph{$O(n)$ total dislocation} with high probability. Besides improving over the previous state-of-the art algorithms -- the best known algorithm had running time $\tilde{O}(n^{3/2})$ -- our result indicates that comparison errors do not make the problem computationally more difficult: a sequence with the best possible dislocation can be obtained in $O(n\log n)$ time and, even without comparison errors, $Ω(n\log n)$ time is necessary to guarantee such dislocation bounds. In order to achieve this optimal result, we solve two sub-problems, and the respective methods have their own merits for further application. One is how to locate a position in which to insert an element in an almost-sorted sequence having $O(\log n)$ maximum dislocation in such a way that the dislocation of the resulting sequence will still be $O(\log n)$. The other is how to simultaneously insert $m$ elements into an almost sorted sequence of $m$ different elements, such that the resulting sequence of $2m$ elements remains almost sorted.

In real world applications, important resources like energy are saved by deliberately using so-called low-cost operations that are less reliable. Some of these approaches are based on a dual mode technology where it is possible to choose between high-energy operations (always correct) and low-energy operations (prone to errors), and thus enable to trade energy for correctness. In this work we initiate the study of algorithms for solving optimization problems that in their computation are allowed to choose between two types of operations: high-energy comparisons (always correct but expensive) and low-energy comparisons (cheaper but prone to errors). For the errors in low-energy comparisons, we assume the persistent setting, which usually makes it impossible to achieve optimal solutions without high-energy comparisons. We propose to study a natural complexity measure which accounts for the number of operations of either type separately. We provide a new family of algorithms which, for a fairly large class of maximization problems, return a constant approximation using only polylogarithmic many high-energy comparisons and only O(n log n) low-energy comparisons. This result applies to the class of p-extendible system s [Mestre, 2006], which includes several NP-hard problems and matroids as a special case (p=1). These algorithmic solutions relate to some fundamental aspects studied earlier in different contexts: (i) the approximation guarantee when only ordinal information is available to the algorithm; (ii) the fact that even such ordinal information may be erroneous because of low-energy comparisons and (iii) the ability to approximately sort a sequence of elements when comparisons are subject to persistent errors. Finally, our main result is quite general and can be parametrized and adapted to other error models.

We present a sorting algorithm for the case of recurrent random comparison errors. The algorithm essentially achieves simultaneously good properties of previous algorithms for sorting n distinct elements in this model. In particular, it runs in O(n^2) time, the maximum dislocation of the elements in the output is O(log n), while the total dislocation is O(n). These guarantees are the best possible since we prove that even randomized algorithms cannot achieve o(log n) maximum dislocation with high probability, or o(n) total dislocation in expectation, regardless of their running time.

Given a set of n sites in the plane, the order-k Voronoi diagram is a planar subdivision such that all points in a region share the same k nearest sites. The order-k Voronoi diagram arises for the k-nearest-neighbor problem, and there has been a lot of work for point sites in the Euclidean metric. In this paper, we study order-k Voronoi diagrams defined by an abstract bisecting curve system that satisfies several practical axioms, and thus our study covers many concrete order-k Voronoi diagrams. We propose a randomized incremental construction algorithm that runs in O(k(n-k) log^2 n +n log^3 n) steps, where O(k(n-k)) is the number of faces in the worst case. Due to those axioms, this result applies to disjoint line segments in the L_p norm, convex polygons of constant size, points in the Karlsruhe metric, and so on. In fact, this kind of run time with a polylog factor to the number of faces was only achieved for point sites in the L_1 or Euclidean metric before.

Rapid growth in capacity makes flow-based microfluidic biochips a promising candidate for biochemical analysis because they can integrate more complex functions. However, as the number of components grows, the total length of flow channels between components must increase exponentially. Recent empirical studies show that long flow channels are vulnerable due to blocking and leakage defects. Thus, it is desirable to minimize the total length of flow channels for robustness. Also, for timing-sensitive biochemical assays, increase in the longest length of flow channel will delay the assay completion time and lead to variation of fluid, thereby affecting the correctness of outcome. The increasing number of components, including the pre-placed components, on the chip makes the flow channel routing problem even more complicated. In this paper, we propose an efficient obstacle-avoiding rectilinear Steiner minimum tree algorithm to deal with flow channel routing problem in flow-based microfluidic biochips. Based on the concept of Kruskal algorithm and formulating the considerations as a bi-criteria function, our algorithm is capable of simultaneously minimizing the total length and the longest length of flow channel.

Given a set of pin-vertices, an obstacle-avoiding rectilinear Steiner minimal tree (OARSMT) connects all the pin-vertices possibly through Steiner points using vertical and horizontal segments with the minimal wirelength and without intersecting any obstacle. To deal with multiple routing layers and preferred routing orientations, we consider the multilayer obstacle-avoiding rectilinear Steiner minimal tree (ML-OARSMT) problem and the obstacle-avoiding preferred direction Steiner tree (OAPD-ST) problem. First, we prove that the multilayer case is theoretically different from the 2D one, and propose a reduction to transform a multilayer instance into a 3D instance. Based on the reduction, we apply computational geometry techniques to develop an efficient algorithm, utilizing existing OARSMT heuristics, for the ML-OARSMT problem and the OAPD-ST problem. Furthermore, we develop an advanced Steiner point selection to avoid inferior Steiner points and to improve the solution quality. Experimental results show that our algorithm provides a solution with excellent quality and has a significant speed-up compared to previously known results.

We investigate the higher-order Voronoi diagrams of n point sites with respect to the geodesic distance in a simple polygon with h > 0 polygonal holes and c corners. Given a set of n point sites, the kth-order Voronoi diagram partitions the plane into several regions such that all points in a region share the same k nearest sites. The nearest-site (first-order) geodesic Voronoi diagram has already been well-studied, and its total complexity is O(n+c). On the other hand, Bae and Chwa [3] recently proved that the total complexity of the farthest-site ((n − 1)st-order) geodesic Voronoi diagram and the number of faces in the diagram are Θ(nc) and Θ(nh), respectively. It is of high interest to know what happens between the first-order and the (n − 1)st-order geodesic Voronoi diagrams. In this paper we prove that the total complexity of the kth-order geodesic Voronoi diagram is Θ(k(n − k) + kc), and the number of faces in the diagram is Θ(k(n − k) + kh). Our results successfully explain the variation from the nearest-site to the farthest-site geodesic Voronoi diagrams, i.e., from k = 1 to k = n − 1, and also illustrate the formation of a disconnected Voronoi region, which does not occur in many commonly used distance metrics, such as the Euclidean, L1, and city metrics. We show that the kth-order geodesic Voronoi diagram can be computed in O(k2(n+c) log(n+c)) time using an iterative algorithm.

We consider the multi-layer obstacle-avoiding rectilinear Steiner minimal tree (OARSMT) problem and propose a reduction to transform a multi-layer instance into a 3D instance. Based on the reduction we apply computational geometry techniques to develop an efficient algorithm, utilizing existing OARSMT heuristics. Experimental results show that our algorithm provides a solution with excellent quality and has a significant speed-up compared to previously known results.

For the obstacle-avoiding rectilinear Steiner minimal tree (OARSMT) problem, we present a Steiner-point-based algorithm that achieves the best practical performance among existing heuristics. We first propose a new concept of Steiner point locations, creating a linear-space routing graph with satisfactory Steiner point candidates to resolve the bottleneck of most existing heuristics. Then, we propose a Steiner-point-based framework to yield a solution, which is close to the key to the handling of the OARSMT problem. Experimental results show that this algorithm achieves excellent solution quality and speed performance at the same time. We also extend the Steiner-point-based framework to the obstacle-avoiding preferred direction Steiner tree problem with a good performance.

For the obstacle-avoiding rectilinear Steiner minimal tree problem, this paper presents an O(n log n)-time algorithm with theoretical optimality guarantees on a number of specific cases, which required O(n3) time in previous works. We propose a new framework to directly generate O(n) critical paths as essential solution components, and prove that those paths guarantee the existence of desirable solutions. The path-based framework neither generates invalid initial solutions nor constructs connected routing graphs, and thus provides a new way to deal with the OARSMT problem. Experimental results show that our algorithm achieves the best speed performance, while the average wirelength of the resulting solutions is only 1.1% longer than that of the best existing solutions.

For the obstacle-avoiding rectilinear Steiner minimal tree (OARSMT) problem, this paper presents a Steiner-point based algorithm to achieve the best practical performance in wirelength and run time. Unlike many previous works, the Steiner-based framework is more focused on the usage of Steiner points instead of the handling of obstacles. This paper also proposes a new concept of Steiner point locations to provide an effective as well as efficient way to generate desirable Steiner point candidates. Experimental results show that this algorithm achieves the best solution quality in Θ (n log n) empirical time, which was originally generated by applying the maze routing on an Ω(n2)-space graph. The Steiner-point based framework and the new concept of Steiner point locations can be applied to future research on the OARSMT problem and its generations, such as the multi-layer OARSMT problem.

Rectilinear Steiner trees are used to route signal nets by global and detail routers in VLSI design for a long time. However, in current IC industry, there are significantly increasing obstacles to be considered, such as large-scale power networks, pre-routed nets, IP blocks, and antenna jumpers. Accordingly, the obstacle-avoiding rectilinear Steiner minimal tree (OARSMT) problem has become more important. In this article, we propose a new routing graph, obstacle-avoiding routing graph (OARG), for the OARSMT problem. Due to the important properties of OARG, we construct a 3-step algorithm and a local refinement scheme, which both can take advantage of these properties, to find a suboptimal solution efficiently. Furthermore, each step of our 3-step algorithm as well as the local refinement scheme has theoretical or practical benefits. Therefore, each of them can be applicable to other existing works for general or specific considerations such as efficiency or effectiveness. Extensive experimental results show that our method outperforms all existing works in terms of wirelength and achieves the best speed performance.

In IC design, rectilinear Steiner trees have been used to route signal nets by global and detail routers for a long time. Recently, there are more complicated processing conditions for routing to be considered, such as multiple routing layers, obstacles, and preferred directions. Furthermore, routability is also an important issue for modern routing which handles more than ten thousand signal nets. As a result, how to meet the processing conditions and consider the routability at the same time is becoming important. In this paper, we formulate a routing problem, called the obstacle-avoiding preferred direction Steiner tree (OAPDST) problem, which can deal with more practical processing conditions and achieve acceptable routability. To the best of our knowledge, this is the first attempt to formulate this problem. Then, we propose a routing graph, called preferred direction evading graph (PDEG), for this problem, and prove that at least one optimal solution can be found on PDEG. As a result, by using PDEG as the solution space, more efficient and effective methods can be found for the OAPDST problem. Based on PDEG, we also construct an approximation algorithm for the OAPDST problem to provide stable and effective solutions. Experimental results show that our method can perform well for the OAPDST problem

The electrostatic discharge (ESD) problem has become a challenging reliability issue in nanometer-circuit design. High voltages that resulted from ESD might cause high current densities in a small device and burn it out, so on-chip protection circuits for IC pads are required. To reduce the design cost, the protection circuit should be added only for the IC pads with an ESD current path, which causes the ESD current path analysis problem. In this paper, we first introduce the analysis problem for ESD protection in circuit design. We then model the circuit as a constraint graph, decompose the ESD connected components (ECCs) linked with the pads, and apply breadth-first search (BFS) to identify the ECCs in each constraint graph and, thus, the current paths. Experimental results show that our algorithm can very efficiently and economically detect all ESD paths. For example, our algorithm can detect all ESD paths in a circuit with more than 1.3 million vertices in 1.39 s and consume only 44-MB memory on a 3.0-GHz Intel Pentium 4 PC. To the best of our knowledge, our algorithm is thefirstpointtoolavailable to the public for the ESD analysis.

The electrostatic discharge (ESD) problem has become a challenging reliability issue in nanometer circuit design. High voltages resulted from ESD might cause high current densities in a small device and burn it out, so on-chip protection circuits for IC pads are required. To reduce the design cost, the protection circuit should be added only for the IC pads with an ESD current path, which arises the ESD current path analysis problem. In this paper, we first introduce the analysis problem for ESD protection in circuit design. We then model the circuit as a constrained graph, decompose ESD connected components linked with the pads, and apply the breadth-first search (BFS) to identify the ESD connected components in each constrained graph and thus the current paths. Experimental results show that our algorithm can detect all ESD paths very efficiently and economically. To our best knowledge, our algorithm is the first point tool available to the public for the ESD analysis.