Search Constraints
« Previous |
1 - 10 of 12
|
Next »
Number of results to display per page
Search Results
-
- Resource Type:
- Article
- Creator:
- Sack, Jörg-Rüdiger, Maheshwari, Anil, and Lingas, A.
- Abstract:
- We provide optimal parallel solutions to several link-distance problems set in trapezoided rectilinear polygons. All our main parallel algorithms are deterministic and designed to run on the exclusive read exclusive write parallel random access machine (EREW PRAM). Let P be a trapezoided rectilinear simple polygon with n vertices. In O(log n) time using O(n/log n) processors we can optimally compute: 1. Minimum réctilinear link paths, or shortest paths in the L1 metric from any point in P to all vertices of P. 2. Minimum rectilinear link paths from any segment inside P to all vertices of P. 3. The rectilinear window (histogram) partition of P. 4. Both covering radii and vertex intervals for any diagonal of P. 5. A data structure to support rectilinear link-distance queries between any two points in P (queries can be answered optimally in O(log n) time by uniprocessor). Our solution to 5 is based on a new linear-time sequential algorithm for this problem which is also provided here. This improves on the previously best-known sequential algorithm for this problem which used O(n log n) time and space.5 We develop techniques for solving link-distance problems in parallel which are expected to find applications in the design of other parallel computational geometry algorithms. We employ these parallel techniques, for example, to compute (on a CREW PRAM) optimally the link diameter, the link center, and the central diagonal of a rectilinear polygon.
- Date Created:
- 1995-09-01
-
- Resource Type:
- Conference Proceeding
- Creator:
- Maheshwari, Anil, Nandy, Ayan, Smid, Michiel, and Das, Sandip
- Abstract:
- Consider a line segment R consisting of n facilities. Each facility is a point on R and it needs to be assigned exactly one of the colors from a given palette of c colors. At an instant of time only the facilities of one particular color are 'active' and all other facilities are 'dormant'. For the set of facilities of a particular color, we compute the one dimensional Voronoi diagram, and find the cell, i.e, a segment of maximum length. The users are assumed to be uniformly distributed over R and they travel to the nearest among the facilities of that particular color that is active. Our objective is to assign colors to the facilities in such a way that the length of the longest cell is minimized. We solve this optimization problem for various values of n and c. We propose an optimal coloring scheme for the number of facilities n being a multiple of c as well as for the general case where n is not a multiple of c. When n is a multiple of c, we compute an optimal scheme in Θ(n) time. For the general case, we propose a coloring scheme that returns the optimal in O(n2logn) time.
- Date Created:
- 2014-01-01
-
- Resource Type:
- Conference Proceeding
- Creator:
- Maheshwari, Anil and Zeh, Norbert
- Abstract:
- We present external memory algorithms for outerplanarity testing, embedding outerplanar graphs, breadth-first search (BFS) and depth-first search (DFS) in outerplanar graphs, and finding a2-separator of size 2 for a given outerplanar graph. Our algorithms take O(sort(N)) I/Os and can easily be improved to take O (perm (N)) I/Os, as all these problems have linear time solutions in internal memory. For BFS, DFS, and outerplanar embedding we show matching lower bounds.
- Date Created:
- 1999-01-01
-
- Resource Type:
- Conference Proceeding
- Creator:
- Maheshwari, Anil, Sack, Jörg-Rüdiger, Lanthier, Mark, and Aleksandrov, Lyudmil
- Date Created:
- 1998-01-01
-
- Resource Type:
- Conference Proceeding
- Creator:
- He, Meng, Dillabaugh, Craig, Zeh, Norbert, and Maheshwari, Anil
- Date Created:
- 2009-12-01
-
- Resource Type:
- Conference Proceeding
- Creator:
- Dillabaugh, Craig, He, Meng, and Maheshwari, Anil
- Abstract:
- We present two results for path traversal in trees, where the traversal is performed in an asymptotically optimal number of I/Os and the tree structure is represented succinctly. Our first result is for bottom-up traversal that starts with a node in the tree T and traverses a path to the root. For blocks of size B, a tree on N nodes, and for a path of length K, we design data structures that permit traversal of the bottom-up path in O(K/B) I/Os using only bits, for an arbitrarily selected constant, ε, where 0∈<∈ε<∈1. Our second result is for top-down traversal in binary trees. We store T using (3∈+∈q)N∈+∈o(N) bits, where q is the number of bits required to store a key, while top-down traversal can still be performed in an asymptotically optimal number of I/Os.
- Date Created:
- 2008-12-01
-
- Resource Type:
- Conference Proceeding
- Creator:
- Bose, Prosenjit, Maheshwari, Anil, Carmi, Paz, Smid, Michiel, and Farshi, Mohammad
- Abstract:
- It is well-known that the greedy algorithm produces high quality spanners and therefore is used in several applications. However, for points in d-dimensional Euclidean space, the greedy algorithm has cubic running time. In this paper we present an algorithm that computes the greedy spanner (spanner computed by the greedy algorithm) for a set of n points from a metric space with bounded doubling dimension in time using space. Since the lower bound for computing such spanners is Ω(n 2), the time complexity of our algorithm is optimal to within a logarithmic factor.
- Date Created:
- 2008-10-27
-
- Resource Type:
- Conference Proceeding
- Creator:
- Couture, Mathieu, Smid, Michiel, Maheshwari, Anil, Bose, Prosenjit, Carmi, Paz, and Zeh, Norbert
- Abstract:
- Given an integer k ≥ 2, we consider the problem of computing the smallest real number t(k) such that for each set P of points in the plane, there exists a t(k)-spanner for P that has chromatic number at most k. We prove that t(2)∈=∈3, t(3)∈=∈2, , and give upper and lower bounds on t(k) for k∈>∈4. We also show that for any ε>∈0, there exists a (1∈+∈ε)t(k)-spanner for P that has O(|P|) edges and chromatic number at most k. Finally, we consider an on-line variant of the problem where the points of P are given one after another, and the color of a point must be assigned at the moment the point is given. In this setting, we prove that t(2)∈=∈3, , , and give upper and lower bounds on t(k) for k∈>∈4.
- Date Created:
- 2008-08-27
-
- Resource Type:
- Conference Proceeding
- Creator:
- Smid, Michiel, Maheshwari, Anil, Das, Sandip, and Banik, Aritra
- Abstract:
- Let P be a simple polygon with m vertices and let be a set of n points in P. We consider the points of to be users. We consider a game with two players and. In this game, places a point facility inside P, after which places another point facility inside P. We say that a user is served by its nearest facility, where distances are measured by the geodesic distance in P. The objective of each player is to maximize the number of users they serve. We show that for any given placement of a facility by, an optimal placement for can be computed in O(m + n(logn + logm)) time. We also provide a polynomial-time algorithm for computing an optimal placement for.
- Date Created:
- 2013-10-08
-
- Resource Type:
- Conference Proceeding
- Creator:
- Zeh, Norbert, Hutchinson, David, and Maheshwari, Anil
- Abstract:
- We present results related to satisfying shortest path queries on a planar graph stored in external memory. In particular, we show how to store rooted trees in external memory so that bottom-up paths can be traversed I/O-efficiently, and we present I/O-efficient algorithms for triangulating planar graphs and computing small separators of such graphs. Using these techniques, we can construct a data structure that allows for answering shortest path queries on a planar graph I/O-efficiently.
- Date Created:
- 1999-01-01