<p>Shiv Nadar University is a comprehensive, multidisciplinary, research-focused, and student-centric University offering a full range of academic programs at the undergraduate, postgraduate and doctoral level. With state-of-the-art infrastructure, the University comprises of academic wings, sophisticated labs, international standard sports facilities, amphitheaters, auditorium, conference rooms and smart classrooms. The University&rsquo;s goal is to become internationally recognized for the quality of its research and creative endeavors and their applicability to improving quality of life, generating new insights and expanding the boundaries of human knowledge creativity. Committed to excellence in teaching, research and service, the University aims to serve the higher education needs of India and the world beyond.</p>

Shiv Nadar University

We describe a very simple deterministic parallel algorithm for linear programming in fixed dimension d that takes poly(log log n) time in the common CRCW PRAM model and does optimal O(n) work. Our algorithm is based on multidimensional search and an effective use of approximation algorithms to speed-up the basic search in the CRCW model. Our method also yields very fast poly(log log n) algorithm for smallest enclosing sphere and approximate ham-sandwich cuts as well as an O(log n) time work-optimal algorithm for exact ham-sandwich cuts of separable point sets. For all these problems, particularly for the fixed-dimensional linear programming, o(log n) time efficient deterministic PRAM algorithms were not known until very recently.

(SoE) School of Engineering

Annual ACM Symposium on Parallel Algorithms and Architectures

Parallel multidimensional search using approximation algorithms: With applications to linear-programming and related problems

In this paper we focus on the problem of designing very fast parallel algorithms for the convex hull problem in two and three dimensions in the arbitrary CRCW model whose running times are output-size sensitive. We present a fast randomized algorithm for planar hulls that runs in expected time O(log H · log log n) and does optimal O(n log H) work where n and H are the input and output sizes respectively. For log H = Ω(log log n), we can achieve the optimal running time of O(log H) for planar hulls while simultaneously keeping the work optimal. In three dimensions, our algorithm runs in expected time O(log log2 n·log H) with optimal O(n log H) work for all H. Hence, for O(logO(1) n) size outputs, our algorithms in two and three dimensions achieve poly(log log n) running time and optimal O(n log log n) work. The previously known output-sensitive work-optimal algorithms for convex hulls have running times Ω(log n) (expected) and Ω(log3 n) in two and three dimensions respectively. Our algorithms assume no input distribution and the running times hold with high probability. We also describe a very simple O(log n log H) time optimal deterministic algorithm for planar hulls which is an improvement for small outputs. For larger output-sizes, a running time of O(log n log log n)) can be achieved.

World University root node

Proceedings of the Annual Symposium on Computational Geometry

Faster output-sensitive parallel convex hulls for d ≤ 3: optimal sublogarithmic algorithms for small outputs

We present an alternative implementation of the fractional cascading data structure of Chazelle and Guibas (Algorithmica1 (1986), 133-162) that performs iterative search for a key in multiple ordered lists. The construction of our data structure uses randomization and simplifies the algorithm of Chazelle and Guibas, vastly making it practical to implement. Although our bounds are asymptotically similar to the earlier ones, there are improvements in the constant factors. Our analysis is novel and captures some of the inherent difficulties associated with the fractional cascading data structure. In particular, we use tools from branching process theory and derive some useful asymptotic bounds. The probability of deviation from the expected performance bounds decreases exponentially with number of keys. Also, under a restricted model, we obtain efficient bounds for updates in the data structure. © 1995 Academic Press, Inc.

Journal of Algorithms

Fractional cascading revisited

In this paper, we present an algorithm for hidden surface removal for a class of polyhedral surfaces which have a property that they can be ordered relatively quickly. For example, our results apply directly to terrain maps. A distinguishing feature of our algorithm is that its running time is sensitive to the actual size of the visible image, rather than the total number of intersections in the image plane which can be much larger than the visible image. The time complexity of this algorithm is O((k + n) log2n) where n and k are, respectively, the input and the output sizes. Thus, in a significant number of situations this will be faster than the worst case optimal algorithms which have running time of Ω(n2) irrespective of the output size. © 1995.

Mathematical and Computer Modelling

An efficient output-sensitive hidden-surface removal algorithm for polyhedral terrains

We show that any parallel algorithm in the fixed degree algebraic decision tree model that answers membership queries in W⊆ Rn using p processors, requires Ω (|W|/nlog(p/n)) rounds where |W| is the number of connected components of W. We further prove a similar result for the average case complexity. We give applications of this result to various fundamental problems in computational geometry like convex-hull construction and trapezoidal decomposition and also present algorithms with matching upper bounds. © 1994, Springer Verlag. All rights reserved.

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Lower bounds for parallel algebraic decision trees, complexity of convex hulls and related problems

We present an O((m + n)√n log n) time algorithm to select the k th smallest item from an m × n totally monotone matrix for any k ≤ ran. This is the first subquadratic algorithm for selecting an item from a totally monotone matrix. Our method also yields an algorithm for generalized row selection in monotone matrices of the same time complexity. Given a set S = {p1, …, pn} of n points in convex position and a vector k = {k1, …, kn}, we also present an O(n4/3 logO(1) n) algorithm to compute the kith nearest neighbor of pi for every i ≤ n; c is an appropriate constant. This algorithm is considerably faster than the one based on a row-selection algorithm for monotone matrices. If the points of S are arbitrary, then the kith h nearest neighbor of pi, for all i ≤ n, can be computed in time O(n7/5 logc n), which also improves upon the previously best-known result. © 1994, Springer Verlag. All rights reserved.

Selection in monotone matrices and computing kth nearest neighbors

We present an optimal algorithm for sorting n integers in the range [1, nc] (for any constant c) for the EREW PRAM model where the word length is nε, for any ε&gt;0. Using this algorithm, the best known upper bound for integer sorting on the (O(log n) word length) EREW PRAM model is improved. In addition, a novel parallel range reduction algorithm which results in a near optimal randomized integer sorting algorthm is presented. For the case when the keys are uniformly distributed integers in an arbitrary range, we give an algorithm whose expected running time is optimal. © 1992 Springer-Verlag.

Acta Informatica

On parallel integer sorting

We present parallel algorithms for some fundamental problems in computational geometry which have a running time of O(log n) using n processors, with very high probability (approaching 1 as n → ∞). These include planar-point location, triangulation, and trapezoidal decomposition. We also present optimal algorithms for three-dimensional maxima and two-set dominance counting by an application of integer sorting. Most of these algorithms run on a CREW PRAM model and have optimal processor-time product which improve on the previously best-known algorithms of Atallah and Goodrich [5] for these problems. The crux of these algorithms is a useful data structure which emulates the plane-sweeping paradigm used for sequential algorithms. We extend some of the techniques used by Reischuk [26] and Reif and Valiant [25] for flashsort algorithm to perform divide and conquer in a plane very efficiently leading to the improved performance by our approach. © 1992 Springer-Verlag New York Inc.

Algorithmica

Optimal randomized parallel algorithms for computational geometry

We present algorithms for maintaining data structures supporting fast (polylogarithmic) point-location and ray-shooting queries in arrangements of hyperplanes. This data structure allows for deletion and insertion of hyperplanes. Our algorithms use random bits in the construction of the data structure but do not make any assumptions about the update sequence or the hyperplanes in the input. The query bound for our data structure is Õ(polylog(n)), where n is the number of hyperplanes at any given time, and the Õ notation indicates that the bound holds with high probability, where the probability is solely with respect to randomization in the data structure. By high probability we mean that the probability of error is inversely proportional to a large degree polynomial in n. The space requirement is Õ(nd). The cost of update is Õ(nd-1 log n. The expected cost of update is O(nd-1); the expectation is again solely with respect to randomization in the data structure. Our algorithm is extremely simple. We also give a related algorithm with optimal Õ(log n) query time, expected O(nd) space requirement, and amortized O(nd-1) expected cost of update. Moreover, our approach has a versatile quality which is likely to have further applications to other dynamic algorithms. For d=2, 3 we also show how to obtain polylogarithmic update time in the CRCW PRAM model so that the processor-time product matches (within a polylogarithmic factor) the sequential update time. © 1992 Springer-Verlag New York Inc.

Fulltext

Discrete & Computational Geometry

Dynamic point location in arrangements of hyperplanes

We give an alternate implementation of the fractional cascading data-structure of Chazelle and Guibas to do iterativesearch for a key in multiple ordered lists. The construction of our data-structure uses randomization and simplifies the algorithm of Chazelle and Guibas vastly making it practical to implement. Although our bounds are asymptotically similar to the earlier ones, there are improvements in the constant factors. Our analysis is novel and captures some of the inherent difficulties associated with the fractional casading data structure. In particular, we use tools from branching process theory and derive some useful asymptotic bounds. The probability of deviation from the expected performance bounds decreases rapidly with number of keys. © Springer-Verlag Berlin Heidelberg 1992.

Fractional cascading simplified

The Skip-list data-structure was proposed by Pugh as an alternate to balanced binary search trees. This remarkably simple data-structure uses randomization and Pugh proved that the expected performance is comparable to the balanced trees. In this note we prove that the performance can be further guaranteed in the following sense: the probability of the search time or space complexity exceeding their expected values, approaches 0 rapidly as the number of keys increases. © 1991.

Information Processing Letters

Some observations on skip-lists

This paper’s main result is an O((√m lg m)(n lg n)+m lg n)-time algorithm for computing the kth smallest entry in each row of an m × n totally monotone array. (A two-dimensional array A = {a[i,j]} is totally monotone if for all i1 &lt; i2 and j1 &lt; j2, a[i1,j1] &lt; a[i1, j2] implies a[i2, j1] &lt; a[i2, j2].) For large values of k (in particular, for k = n/2'|), this algorithm is significantly faster than the O(k(m + n))-time algorithm for the same problem due to Kravets and Park (1991). An immediate consequence of this result is an O(n3/2 lg2 n)-time algorithm for computing the kth nearest neighbor of each vertex of a convex n-gon. In addition to the main result, we also give an O(n lg m)-time algorithm for computing an approximate median in each row of an m × n totally monotone array; this approximate median is an entry whose rank in its row lies between [n/4] and [3n/4]. © Springer-Verlag Berlin Heidelberg 1991.

Improved selection in totally monotone arrays

Given n elements from a totally ordered set we outline a method for choosing an element whose rank is γn for some 0 &lt;γ&lt;1 where γ is independent of n. The algorithm executes in constant time in a CRCW PRAM model using a linear number of processors and succeeds with probability 1 - n-c for any c&gt;0. © 1990.

Finding an approximate median with high probability in constant parallel time

There are now a number of fundamental problems in computational geometry that have optimal algorithms on PRAM models. We present randomized parallel algorithms which execute on an n-processor butterfly inter-connection network in O(log n) time for the following problems of input size n: trapezoidal decomposition, visibility, triangulation and 2-D convex hull. These are based on some previous work of the authors on PRAM algorithms and a new algorithm for doing binary search on fixed connection network. Apart from a 2-D convex hull algorithm, these are the first non-trivial geometric algorithms which attain this performance on fixed connection networks. The techniques developed in this paper rely on random sampling methods to do load-balancing on fixed-connection networks; it seems likely that they will have wider applications.

Algorithms and Architectures

Randomized algorithms for binary search and load balancing on fixed connection networks with geometric applications

Shear-sort opened new avenues in the research of sorting techniques for meshconnected processor arrays. The algorithm is extremely simple and converges to a snake-like sorted sequence with a time complexity which is suboptimal by a logarithmic factor. The techniques used for analyzing shear-sort have been used to derive more efficient algorithms, which have important ramifications both from practical and theoretical viewpoints. Although the algorithms described apply to any general two-dimensional computational model, the focus of most discussions is on meshconnected computers which are now commercially available. In spite of a rich history of 0(n) sorting algorithms on an n × n SIMD mesh, the constants associated with the leading term (i.e., n) are fairly large. This had led researchers to speculate about the tightness of the lower bound. The work in this paper sheds some more light on this problem as a 4n-step algorithm is shown to exist for a model slightly more powerful than the conventional SIMD model. Moreover, this algorithm has a running time of 3n steps on the more powerful MIMD model, which is “truly” optimal for such a model. © 1989 IEEE

IEEE Transactions on Computers

Parallel Sorting in Two-Dimensional VLSI Models of Computation

The recently discovered Shear-sort algorithm requires log2n iterations of row and column sorts for ordering n2 elements on an n × n mesh-connected array of processors. Although the method is extremely simple and practical, it falls short by a factor of log2n of the well-known lower bound for sorting on a mesh-connected computer. Recursive application of Shear-sort in a square array leads to the first proposed O(n) algorithm. A slightly more complicated iterative algorithm, also executing in O(n) steps is presented next. Both algorithms are surprisingly simple and are the result of the adoption of an entirely new approach to two-dimensional sorting. © 1989.

Journal of Parallel and Distributed Computing

Two nearly optimal sorting algorithms for mesh-connected processor arrays using shear-sort

Randomization offers elegant solutions to some problems in parallel computing. In addition to improved efficiency it often leads to simpler and practical algorithms. In this paper we discuss some of the characteristics of randomized algorithms and also give applications in computational geometry where use of randomization gives us significant advantage over the best known deterministic parallel algorithms. © Springer-Verlag Berlin Heidelberg 1989.

Randomization in parallel algorithms and its impact on computational geometry

Polling: A new randomized sampling technique for computational geometry

In this paper we present an algorithm for hidden surface removal for a class of polyhedral surfaces which have a property that they can be ordered relatively quickly like the terrain maps. A distinguishing feature of this algorithm is that its running time is sensitive to the actual size of the visible image rather than the total number of intersections in the image plane which can be much larger than the visible image. The time complexity of this algorithm is O((k +n) log n log log n) where n and k are respectively the input and the output sizes. Thus, in a significant number of situations this will be faster than the worst case optimal algorithms which have running time Ω(n2) irrespective of the output size (where as the output size k is O(n2) only in the worst case). We also present a parallel algorithm based on a similar approach which runs in time O(log4(n+k)) using O((n + k)/log(n+k)) processors in a CREW PRAM model. All our bounds are obtained using ammortized analysis. © 1988 ACM.

Proceedings of the 4th Annual Symposium on Computational Geometry, SCG 1988

An efficient output-sensitive hidden-surface removal algorithm and its parallelization

Given a sequence of numbers which can be mapped into an m multiplied by n array, sorting rows and columns is shown to yield an overall sorted sequence. This unusually simple procedure is shown to require O(log//2 m) iterations by analyzing the data movement in the array under successive row and column sorts. An efficient bubble sort network suitable for VLSI implementation, with near-optimal area-time**2 performance, is a direct application of the row-column sorting technique. The ease of implementation for practical VLSI chips is also demonstrated.