Search Constraints

Start Over
Filtering by: Creator Maheshwari, Anil Remove constraint Creator: Maheshwari, Anil Language English Remove constraint Language: English

Search Results

  • Optimal parallel algorithms for rectilinear link-distance problems

    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

  • A facility coloring problem in 1-D

    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

  • External memory algorithms for outerplanar graphs

    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

  • An ϵ - Approximation algorithm for weighted shortest paths on polyhedral surfaces

    Resource Type:
    Conference Proceeding
    Creator:
    Maheshwari, Anil, Sack, Jörg-Rüdiger, Lanthier, Mark, and Aleksandrov, Lyudmil
    Date Created:
    1998-01-01

  • I/O and space-efficient path traversal in planar graphs

    Resource Type:
    Conference Proceeding
    Creator:
    He, Meng, Dillabaugh, Craig, Zeh, Norbert, and Maheshwari, Anil
    Date Created:
    2009-12-01

  • Succinct and I/O efficient data structures for traversal in trees

    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

  • Computing the greedy spanner in near-quadratic time

    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

  • Geometric spanners with small chromatic number

    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

  • The discrete voronoi game in a simple polygon

    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

  • An external memory data structure for shortest path queries

    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

  • I/O-efficient shortest path queries in geometric spanners

    Resource Type:
    Conference Proceeding
    Creator:
    Smid, Michiel, Zeh, Norbert, and Maheshwari, Anil
    Abstract:
    We present I/O-efficient algorithms to construct planar Steiner spanners for point sets and sets of polygonal obstacles in the plane, and for constructing the “dumbbell” spanner of [6] for point sets in higher dimensions. As important ingredients to our algorithms, we present I/O efficient algorithms to color the vertices of a graph of bounded degree, answer binary search queries on topology buffer trees, and preprocess a rooted tree for answering prioritized ancestor queries.
    Date Created:
    2001-01-01

  • Succinct orthogonal range search structures on a grid with applications to text indexing

    Resource Type:
    Conference Proceeding
    Creator:
    Bose, Prosenjit, Maheshwari, Anil, He, Meng, and Morin, Pat
    Abstract:
    We present a succinct representation of a set of n points on an n×n grid using bits to support orthogonal range counting in time, and range reporting in time, where k is the size of the output. This achieves an improvement on query time by a factor of upon the previous result of Mäkinen and Navarro [1], while using essentially the information-theoretic minimum space. Our data structure not only can be used as a key component in solutions to the general orthogonal range search problem to save storage cost, but also has applications in text indexing. In particular, we apply it to improve two previous space-efficient text indexes that support substring search [2] and position-restricted substring search [1]. We also use it to extend previous results on succinct representations of sequences of small integers, and to design succinct data structures supporting certain types of orthogonal range query in the plane.
    Date Created:
    2009-09-14