Search

Fast aggregation of data with many dimensions is a key component of many applications. The R-tree is the traditional data structure for indexing multi-dimensional data, but even the best R-tree variants suffer from performance degradation as the number of dimensions increases. The DC-tree addressed this issue by replacing Minimum Bounding Rectangle (MBR) keys with Minimum Describing Subsets (MDSs), which are less susceptible to overlap. This technique dramatically improves query performance with many dimensions, but at the cost of reduced insertion performance. Like most R-tree variants, this insertion overhead comes from expensive geometric comparisons while selecting the best child for insertion, or splitting over-full nodes. DC-trees, including the parallel PDC-tree, suffer even more from this overhead since MDSs are typically much more expensive to compare and manipulate than MBRs. This paper introduces the Hilbert PDC-tree, a parallel index structure for many-dimensional data that supports high-velocity data ingestion. This is achieved by avoiding geometric comparisons during insertion by instead inserting records based on the Hilbert index of their keys. This approach is similar to that of the Hilbert R-tree, but with special considerations for efficiently supporting many hierarchical dimensions. Additionally, a new node splitting algorithm significantly reduces overlap and improves query performance. Experiments show that the Hilbert PDC-tree scales well to a high number of dimensions, while supporting a much higher rate of ingestion and better query performance than the PDC-tree.

Fixed-parameter tractability (FPT) techniques have recently been successful in solving NP-complete problem instances of practical importance which were too large to be solved with previous methods. In this paper, we show how to enhance this approach through the addition of parallelism, thereby allowing even larger problem instances to be solved in practice. More precisely, we demonstrate the potential of parallelism when applied to the bounded-tree search phase of FPT algorithms. We apply our methodology to the k-Vertex Cover problem which has important applications in, for example, the analysis of multiple sequence alignments for computational biochemistry. We have implemented our parallel FPT method for the k-Vertex Cover problem using C and the MPI communication library, and tested it on a 32-node Beowulf cluster. This is the first experimental examination of parallel FPT techniques. As part of our experiments, we solved larger instances of k-Vertex Cover than in any previously reported implementations. For example, our code can solve problem instances with k⩾400 in less than 1.5h.

Blockwise access to data is a central theme in the design of efficient ex- ternal memory (EM) algorithms. A second important issue, when more than one disk is present, is fully parallel disk I/O. In this paper we present a simple, deterministic simulation technique which transforms certain Bulk Synchronous Parallel (BSP) algorithms into efficient parallel EM algorithms. It optimizes blockwise data access and parallel disk I/O and, at the same time, utilizes multiple processors connected via a communication network or shared memory. We obtain new improved paral- lel EM algorithms for a large number of problems including sorting, permutation, matrix transpose, several geometric and GIS problems including three-dimensional convex hulls (two-dimensional Voronoi diagrams), and various graph problems. We show that certain parallel algorithms known for the BSP model can be used to ob- tain EM algorithms that meet well known I/O complexity lower bounds for various problems, including sorting.

We present a parallel algorithm for solving thenext element search problemon a set of line segments, using a BSP-like model referred to as thecoarse grained multicomputer(CGM). The algorithm requiresO(1) communication rounds (h-relations withh=O(n/p)),O((n/p)logn) local computation, andO((n/p)logp) memory per processor, assumingn/p?p. Our result implies solutions to the point location, trapezoidal decomposition, and polygon triangulation problems. A simplified version for axis-parallel segments requires onlyO(n/p) memory per processor, and we discuss an implementation of this version. As in a previous paper by Develliers and Fabri (Int. J. Comput. Geom. Appl.6(1996), 487?506), our algorithm is based on a distributed implementation of segment trees which are of sizeO(nlogn). This paper improves onop. cit.in several ways: (1) It studies the more general next element search problem which also solves, e.g., planar point location. (2) The algorithms require onlyO((n/p)logn) local computation instead ofO(logp*(n/p)logn). (3) The algorithms require onlyO((n/p)logp) local memory instead ofO((n/p)logn).

We present a randomized parallel algorithm for constructing the three-dimensional convex hull on a generic p-processor coarse-grained multicomputer with arbitrary interconnection network and n/p local memory per processor, where n/p ? p 2+? (for some arbitrarily small ? > 0). For any given set of n points in 3-space, the algorithm computes the three-dimensional convex hull, with high probability, in $O((n\log{n})/p)$ local computation time and O(1) communication phases with at most O(n/p) data sent/received by each processor. That is, with high probability, the algorithm computes the three-dimensional convex hull of an arbitrary point set in time $O((n\log n)/{p} + \Gamma_{n,p})$ , where Γ n,p denotes the time complexity of one communication phase. The assumption n/p ? p 2+? implies a coarse-grained, limited parallelism, model which is applicable to most commercially available multiprocessors. In the terminology of the BSP model, our algorithm requires, with high probability, O(1) supersteps, synchronization period $L = \Theta((n\log n)/{p})$ , computation cost $O((n\log n)/{p})$ , and communication cost O((n/p) g).

In this paper we study the problem of computing an exact, or arbitrarily close to exact, solution of an unrestricted point set stereo matching problem. Within the context of classical approaches like the Marr-Poggio algorithm, this means that we study how to solve the unrestricted basic subproblems created within such approaches, possibly yielding an improved overall performance of such methods. We present an O(n2 + 4k) time and O(n4) space algorithm for exact unrestricted stereo matching, where n represents the number of points in each set and k the number of depth levels considered. We generalize the notion of a δ-approximate solution for point set congruence to the stereo matching problem and present an O (( e δ ) k n 2 + 2k ) time and O (( e δ )n 2 ) space δ-approximate algorithm for unrestricted stereo matching (e represents measurement inaccuracies in the image). We introduce new computational geometry tools for stereo matching: the translation square arrangement, approximate translation square arrangement and approximate stereo matching tree.

We present a randomized parallel list ranking algorithm for distributed memory multiprocessors, using a BSP type model. We first describe a simple version which requires, with high probability, log(3p)+log ln(n)=O(logp+log logn) communication rounds (h-relations withh=O(n/p)) andO(n/p)) local computation. We then outline an improved version that requires high probability, onlyr⩽(4k+6) log(2/3p)+8=O(k logp) communication rounds wherek=min{i⩾0 |ln(i+1)n⩽(2/3p)2i+1}. Notek

Geometric hashing methods provide an efficient approach to indexing from image features into a database of models. The hash functions that have typically been used involve quantization of the values, which can result in nongraceful degradation of the performance of the system in the presence of noise. Intuitively, it is desirable to replace the quantization of hash values and the resulting binning of hash entries by a method that gives increasingly less weight to a hash table entry as a hashed feature becomes more distant from the hash entry position. In this paper, we show how these intuitive notions can be translated into a well-founded Bayesian approach to object recognition and give precise formulas for the optimal weight functions that should be used in hash space. These extensions allow the geometric hashing method to be viewed as a Bayesian maximum-likelihood framework. We demonstrate the validity of the approach by performing similarity-invariant object recognition using models obtained from drawings of military aircraft and automobiles and test images from real-world grayscale images of the same aircraft and automobile types. Our experimental results represent a complete object recognition system, since the feature extraction process is automated. Our system is scalable and works rapidly and very efficiently on an 8K-processor CM - 2, and the quality of results using similarity-invariant model matching is excellent.

We study the problem of finding shortest paths in time-dependent networks with edge load forecasts where the behavior of each edge is modeled as a time-dependent arrival function with FIFO property. Here, we present a new algorithm that computes for a given start node s and destination node d, the shortest paths and earliest arrival times for all possible starting times. Our algorithm runs in time O((Fd + λ)(|E| + |V| log |V|)) where Fd is the output size (number of linear pieces needed to represent the earliest arrival time function) and λ is the input size (number of linear pieces needed to represent the local earliest arrival time functions for all edges in the network). Our method improves significantly on the best previously known algorithm which requires time O(Fmax |V||E|) where Fmax ≥ Fd is the maximum number of linear pieces needed to represent the earliest arrival time function between the start node s to any node in the network. It has been conjectured that there are cases where Fmax is of super-polynomial size; however, even in such cases, Fd might still be of linear size. In such cases, our algorithm would take polynomial time to find the solution, while other methods require super-polynomial time. Both of the above methods are not useful in practice for graphs where Fd is of super-polynomial size. For such graphs, we present the first approximation method to compute for all possible starting times at s, the earliest arrival times at d within error at most e. Our algorithm runs in time O(Δ/e(|E| + |V|log|V|)) where Δ is the difference between the earliest arrival times at d for the latest and earliest starting times at s.

In this paper, we present optimal parallel algorithms for optical clustering on a mesh-connected computer.Optical clustering is a clustering technique based on the principal of optical resolution, and is of particular interest in picture analysis. The algorithms we present are based on the application of parallel algorithms in computational geometry and graph theory. In particular, we show that given a setS ofN points in the Euclidean plane, the following problems can be solved in optimal\(O\left( {\sqrt N } \right)\) time on a mesh-connected computer of sizeN. 1. Determine the optical clusters ofS with respect to a given separation parameter. 2. Given an interval [a, b] representing the number of optical clusters desired in the clustering ofS, determine the range of the separation parameter that will result in such an optical clustering.

Adigitized plane ź of sizeM is a rectangular źM × źM array of integer lattice points called pixels. A źM × źM mesh-of-processors in which each processorPij represents pixel (i,j) is a natural architecture to store and manipulate images in ź; such a parallel architecture is called asystolic screen. In this paper we consider a variety of computational-geometry problems on images in a digitized plane, and present optimal algorithms for solving these problems on a systolic screen. In particular, we presentO(źM)-time algorithms for determining all contours of an image; constructing all rectilinear convex hulls of an image (peeling); solving the parallel and perspective visibility problem forn disjoint digitized images; and constructing the Voronoi diagram ofn planar objects represented by disjoint images, for a large class of object types (e.g., points, line segments, circles, ellipses, and polygons of constant size) and distance functions (e.g., allLp metrics). These algorithms implyO(źM)-time solutions to a number of other geometric problems: e.g., rectangular visibility, separability, detection of pseudo-star-shapedness, and optical clustering. One of the proposed techniques also leads to a new parallel algorithm for determining all longest common subsequences of two words.

The main problem for the design of dictionary machines on coarse grained hypercube multiprocessors, in comparison to the widely studied dictionary problem for fine grained hypercube multiprocessors, is that due to unequal distribution of the inserted and deleted records, the sizes of the sets stored at the individual processors may vary considerably. This problem, which is usually referred to as the load balancing problem , may lead to considerable degradation of the dictionary machine's performance. In this note we show that the load balancing problem for coarse grained hypercube dictionary machines can be solved with provable bounds on the sizes of the data sets, and with only little computational overhead.

Consider an×n binary image. Given a directionD, the parallel visibility problem consists of determining for each pixel of the image the portion that is visible (i.e., not obstructed by any other black pixel of the image) in directionD from infinity. A related problem, referred to as point visibility, is to compute for each pixel the portion that is visible from a given pointp. In this paper, we deriveO(logn) time SIMD algorithms for each of these two problems on the hypercube, where one processor is assigned to every pixel of the image. Since the worst case communication distance of two processors in an 2-processor hypercube is 2 logn, it follows that both of the above algorithms are asymptotically optimal.

We present the first parallel algorithm for building a Hausdorff Voronoi diagram (HVD). Our algorithm is targeted towards cluster computing architectures and computes the Hausdorff Voronoi diagram for non-crossing objects in time O((n log4 n)/p) for input size n and p processors. In addition, our parallel algorithm also implies a new sequential HVD algorithm that constructs HVDs for non-crossing objects in time O(n log4 n). This improves on previous sequential results and solves an open problem posed by Papadopoulou and Lee (2004)

This paper presents an algorithm, that constructs all Voronoi diagrams for k nearest neighbor searching in the Euclidean plane simultaneously. Its space and time complexity of O(N4) is shown to be optimal.

In this paper, we study the cluster editing problem which is fixed parameter tractable. We present the first practical implementation of a FPT based method for cluster editing, using the approach in [6,7], and compare our implementation with the straightforward greedy method and a solution based on linear programming [3]. Our experiments show that the best results are obtained by using the refined branching method in [7] together with interleaving (re-kernelization). We also observe an interesting lack of monotonicity in the running times for “yes” instances with increasing values of k.

We describe an algorithm for the Feedback Vertex Set problem on undirected graphs, parameterized by the size k of the feedback vertex set, that runs in time O(ckn3) where c=10.567 and n is the number of vertices in the graph. The best previous algorithms were based on the method of bounded search trees, branching on short cycles. The best previous running time of an FPT algorithm for this problem, due to Raman, Saurabh and Subramanian, has a parameter function of the form 2O( klogk / loglogk). Whether an exponentially linear in k FPT algorithm for this problem is possible has been previously noted as a significant challenge. Our algorithm is based on the new FPT technique of iterative compression. Our result holds for a more general “annotated” form of the problem, where a subset of the vertices may be marked as not to belong to the feedback set. We also establish “exponential optimality” for our algorithm by proving that no FPT algorithm with a parameter function of the form O(2o(k)) is possible, unless there is an unlikely collapse of parameterized complexity classes, namely FPT =M[1].

Dehne et al. present a BSP/CGM algorithm for computing a spanning tree and the connected components of a graph, that requires O(log p) communication rounds, where p is the number of processors. It requires the solution of the Euler tour problem which in turn is based on the solution of the list ranking problem. We present a new approach that does not need to solve the Euler tour or the list ranking problem. It is based on the integer sorting algorithm which can be implemented efficiently on the BSP/CGM model [1].

In this paper we present a parallel wavefront algorithm for computing an alignment between two strings A and C, with |A| = m and |C| = n. On a distributed memory parallel computer of p processors each with O((m + n)/p) memory, the proposed algorithm requires O(p) communication rounds and O(mn/p) local computing time. The novelty of this algorithm is based on a compromise between the workload of each processor and the number of communication rounds required, expressed by a parameter called α. The proposed algorithm is expressed in terms of this parameter that can be tuned to obtain the best overall parallel time in a given implementation. We show very promising experimental results obtained on a 64-node Beowulf machine. A characteristic of the wavefront communication requirement is that each processor communicates with few other processors. This makes it very suitable as a potential application for grid computing.

Fixed-parameter tractability (FPT) techniques have recently been successful in solving NP-complete problem instances of practical importance which were too large to be solved with previous methods. In this paper we show how to enhance this approach through the addition of parallelism, thereby allowing even larger problem instances to be solved in practice. More precisely, we demonstrate the potential of parallelism when applied to the bounded-tree search phase of FPT algorithms. We apply our methodology to the k-VERTEX COVER problem which has important applications, e.g., in multiple sequence alignments for computational biochemistry. We have implemented our parallel FPT method for the k-VERTEX COVER problem using C and the MPI communication library, and tested it on a PC cluster. This is the first experimental examination of parallel FPT techniques. We have tested our parallel k-VERTEX COVER method on protein sequences obtained from the National Center for Biotechnology Information. As part of our experiments, we solved larger instances of k-VERTEX COVER than in any previously reported implementations. For example, our code can solve problem instances with k /spl ges/ 400 in less than 1.5 hours. Since our parallel FPT algorithm requires only very little communication between processors, we expect our method to also perform well on Grids.

An FPT algorithm with a running time of O(n 4 + 2 O(k) n 2.5) is described for the Set Splitting problem, parameterized by the number k of sets to be split. It is also shown that there can be no FPT algorithm for this problem with a running time of the form 2 o(k) n c unless the satisfiability of n-variable 3SAT instances can be decided in time 2 o(n).

We present parallel computational geometry algorithms that are scalable, architecture independent, easy to implement, and have, with high probability, an optimal time complexity for uniformly distributed random input data. Our methods apply to multicomputers with arbitrary interconnection network or bus system. The following problems are studied in this paper: (1) lower envelope of line segments, (2) visibility of parallelepipeds, (3) convex hull, (4) maximal elements, (5) Voronoi diagram, (6) all-nearest neighbors, (7) largest empty circle, and (8) largest empty hyperrectangle. Problems 2-8 are studied for d-dimensional space, d=O(1). We implemented and tested the lower envelope algorithm and convex hull algorithm (for d=3 and d=4) on a CM5. The results indicate that our methods are of considerable practical relevance. >

Image processin9 is one of the major fields of application for parallel processing. Some of the first multiprocessors were mainly built for processing images (e.g., the MPP for analyzing LANDSAT satellite data) because for such applications data volumes are often so large that the use of standard sequential machines becomes impracticable. In addition to standard image processing operations such as noise removal, edge detection, filtering, etc., researchers have recently also started to study other "high-level" geometric operations which are well known in computational 9eometry. This special issue of Algorithmica is devoted to parallel algorithms for computational-geometry problems on digitized pictures. The motivation for studying such operations is that in practice geometric data for computationalgeometry applications is often given in the form of an image; hence, parallel algorithms which can be applied directly to the image may be more efficient than applying "standard" parallel computational-geometry methods which require that the image is first converted into, e.g., a set of polygonal chains. For example, consider the standard path-plannin9 problem in robotics: given a set of simple polygons in the plane representing the obstacles and a polygon representing the robot, find the shortest path for the robot to move from point A to point B without colliding with any obstacle. In practice, the robot might be moving in a factory hall; instead of first creating a polygonal description of the obstacles and the robot, it may be more efficient to use as input an image obtained from a camera mounted to the ceiling of the factory. Using an image from a camera might also be more practical for dynamic environments where the locations and shapes of the obstacles are changing. Since the factory, and thus the image of the obstacles, could be very large and the robot's path has to be determined in real-time, a parallel method for solving the path-planning problem directly on the image is desirable. 2 When solving computational-geometry problems for images in parallel, researchers have several different types of parallel machines available. The papers selected for this special issue consider four very commonly used ones: the parallel

The problem of solving System of Linear Algebraic Equations (SLAE) by parallel Monte Carlo numerical methods is considered. Three Monte Carlo algorithms are presented. In case when copy of the matrix is sent to each processor the execution time for solving SLAE by Monte Carlo on p processors is bounded by O(nNT/p) (excluding the initial loading of the data) where N is the number of chains and T is the length of the chain in the stochastic process, which are independent of matrix size n.

In this paper we study parallel algorithms for the Mesh-of-Processors architecture to solve visibility and related separability problems for sets of simple polygons in the plane. In particular, we present the following algorithms: All proposed algorithms are asymptotically optimal (for the Mesh-of-Processors) with respect to time and number of processors.

Consider a set S of n points in the Euclidean plane. We obtain efficient parallel algorithms for the following two problems: (i) compute the contour spanned by the maximal elements of S, and (ii) compute the number of dominated points for every element of S (ECDF searching problem). Both algorithms run in O(n 1 2 ) time on a mesh of n processors, which is asymptotically optimal since any nontrivial computation requires Ω( n 1 2 ) time on the mesh. The algorithms can be generalized to solved the d-dimensional maximal elements and ECDF searching problem in O(n 1 2 + log 2 ( d −2) )( d > 2) time.

Dehne (1986) presented an optimal O(√ n ) time parallel algorithm for solving the ECDF searching problem for a set of n points in two- and three-dimensional space on a mesh-of-processors of size n . However, it remained an open problem whether such an optimal solution exists for the d -dimensional ECDF searching problem for d ⩾4. In this paper we solve this problem by presenting an optimal O(√ n ) time parallel solution to the d -dimensional ECDF searching problem for arbitrary dimension d = O(1) on a mesh-of-processors of size n . The algorithm has several interesting implications. Among others, the following problems can now be solved on a mesh-of-processors in (asymptotically optimal) time O(√ n ) for arbitrary dimension d = O(1): the d -dimensional maximal element determination problem, the d -dimensional hypercube containment counting problem, and the d -dimensional hypercube intersection counting problem. The latter two problems can be mapped to the 2 d -dimensional ECDF searching problem but require an efficient solution to this problem for at least d ⩾4.

The time complexity of searching a sorted list ofn elements in parallel on a coarse grained network of diameterD and consisting ofN processors (wheren may be much larger thanN) is studied. The worst case period and latency of a sequence of pipeline search operation are easity seen to be Ω(logn−logN) and Ω(D+logn−logN), respectively. Since forn=N1+Ω(1) the worst-case period is Ω(logn) (which can be achieved by a single processor), coarse-grained networks appear to be unsuitable for the search problem. By contrast, it is demonstrated using standard queuing theory techniques that a constant expected period can be achieved provided thatn=O(N2N).

Clustering of geometric objects is a very familiar and important problem in many different areas of applications as well as in the theoretical foundation of some modern fields of computer science. This paper describes how design problems, especially the design of an assembly line, can be transformed into a clustering problem. In order to solve the problem for large sizes of input data we introduce a structure, called Voronoi Tree, which applied to our real world data (assembly line design) did not only reduce the time to get a feasible design of an assembly line dramatically, but additionally increased the value of the design by more than 30% (in comparison with standard design methods). In addition to this we introduce a clustering method which is of interest for those applications which can be transformed to planar clustering problems. In this particular case it is possible to compute an (hierarchically) optimized clustering with resp. to a large class of clustering measures in timeO(nn1/2log3n+UF(n)nn1/2+PF(n)) [n: number of points;UF(n), PF(n) dependent on the chosen clustering measure].

The Voronoi diagram of n sites on the surface of a cone has a combinatorial structure rather different from the planar one. We present a sweepcircle algorithm that enables its computation within optimal time O(n log n), using linear storage.

We survey computational geometry algorithms developed for various models of parallel computation including the PRAM, hypercube, mesh-of-processors, linear processor array, mesh of trees, and pyramid.

In this paper, we present a systolic algorithm for computing the configuration space of an arrangement of arbitrary obstacles in the plane for a rectilinearly convex robot. The obstacles and the robot are assumed to be represented in digitized form by a √n × √n nibary image. The algorithm is designed for a Mesh-of-Processors architecture with n processors (using the canonical representation of an image on a processor array) and has an execution time of O(√n) which is asymptotically optimal.

We describe an algorithm for the Feedback Vertex Set problem on undirected graphs, parameterized by the size k of the feedback vertex set, that runs in time O(ckn3) where c = 10.567 and n is the number of vertices in the graph. The best previous algorithms were based on the method of bounded search trees, branching on short cycles. The best previous running time of an FPT algorithm for this problem, due to Raman, Saurabh and Subramanian, has a parameter function of the form 2O(k log k /log log k). Whether an exponentially linear in k FPT algorithm for this problem is possible has been previously noted as a significant challenge. Our algorithm is based on the new FPT technique of iterative compression. Our result holds for a more general form of the problem, where a subset of the vertices may be marked as forbidden to belong to the feedback set. We also establish "exponential optimality" for our algorithm by proving that no FPT algorithm with a parameter function of the form O(2o(k)) is possible, unless there is an unlikely collapse of parameterized complexity classes, namely FPT = M[1].

In this paper we study parallel algorithms for the Mesh-of-Processors architecture to solve visibility and related separability problems for sets of simple polygons in the plane. In particular, we present the following algorithms: All proposed algorithms are asymptotically optimal (for the Mesh-of-Processors) with respect to time and number of processors.

The Transversal problem, i.e, the enumeration of all the minimal transversals of a hypergraph in output-polynomial time, i.e, in time polynomial in its size and the cumulated size of all its minimal transversals, is a fifty years old open problem, and up to now there are few examples of hypergraph classes where the problem is solved. A minimal dominating set in a graph is a subset of its vertex set that has a non empty intersection with the closed neighborhood of every vertex. It is proved in [M. M. Kant\'e, V. Limouzy, A. Mary, L. Nourine, On the Enumeration of Minimal Dominating Sets and Related Notions, In Revision 2014] that the enumeration of minimal dominating sets in graphs and the enumeration of minimal transversals in hypergraphs are two equivalent problems. Hoping this equivalence can help to get new insights in the Transversal problem, it is natural to look inside graph classes. It is proved independently and with different techniques in [Golovach et al. - ICALP 2013] and [Kant\'e et al. - ISAAC 2012] that minimal edge dominating sets in graphs (i.e, minimal dominating sets in line graphs) can be enumerated in incremental output-polynomial time. We provide the first polynomial delay and polynomial space algorithm that lists all the minimal edge dominating sets in graphs, answering an open problem of [Golovach et al. - ICALP 2013]. Besides the result, we hope the used techniques that are a mix of a modification of the well-known Berge's algorithm and a strong use of the structure of line graphs, are of great interest and could be used to get new output-polynomial time algorithms., Comment: proofs simplified from previous version, 12 pages, 2 figures