Geodesic Paths On 3D Surfaces: Survey and Open Problems (2009)
Maheshwari, Anil, Wuhrer, Stefanie
This survey gives a brief overview of theoretically and practically relevant algorithms to compute geodesic paths and distances on three-dimensional surfaces. The survey focuses on polyhedral...
Algorithms for Packing Two Circles in a Convex Polygon (2009)
Prosenjit Bose, Jurek Czyzowicz, Evangelos Kranakis, Anil Maheshwari
3
Approximate Shortest Path Queries on Weighted Polyhedral Surfaces ⋆ (2009)
Lyudmil Aleks, Hristo N. Djidjev, Hua Guo, Anil Maheshwari, Doron Nussbaum, Jörg-rüdiger Sack
Abstract. We consider the classical geometric problem of determining shortest paths between pairs of points lying on a weighted polyhedral surface P consisting of n triangular faces. We present query...
Linear-Space Algorithms for Distance Preserving Embedding ∗ (2008)
Tetsuo Asano, Prosenjit Bose, Paz Carmi, Anil Maheshwari, Chang Shu, Michiel Smid, ...
The distance preserving graph embedding problem is to embed vertices of a given weighted graph into points in 2-dimensional Euclidean space so that for each edge the distance between their...
Cutting Circles into Equal Area Pieces 1 Prosenjit Bose (2008)
Evangelos Kranakis, Danny Krizanc, Anil Maheshwari, Jurek Czyzowicz
We study several problems related to cutting circles into equal area pieces. Our objective is to minimize the total length of the cuts.
A Linear-Space Algorithm for Distance Preserving Graph Embedding ∗ (2008)
Tetsuo Asano, Prosenjit Bose, Paz Carmi, Anil Maheshwari, Chang Shu, Michiel Smid, ...
The distance preserving graph embedding problem is to embed vertices of a given weighted graph into points in d-dimensional Euclidean space for a constant d so that for each edge the distance between...
A Coarse Grained Parallel Algorithm for Hausdorff Voronoi Diagrams (2008)
Frank Dehne, Anil Maheshwari, Ryan Taylor
Abstract — 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...
Experiments with a Parallel External Memory System ⋆ (2008)
Mohammad R. Nikseresht, David A. Hutchinson, Anil Maheshwari
Abstract. The theory of bulk-synchronous parallel computing has produced a large number of attractive algorithms, which are provably optimal in some sense, but typically require that the aggregate...
Succinct Geometric Indexes Supporting Point Location Queries (2008)
Bose, Prosenjit, Chen, Eric Y., He, Meng, Maheshwari, Anil, Morin, Pat
We propose to design data structures called succinct geometric indexes of negligible space (more precisely, o(n) bits) that, by taking advantage of the n points in the data set permuted and stored...
Approximation Algorithms for Shortest Descending Paths in Terrains (2008)
Ahmed, Mustaq, Das, Sandip, Lodha, Sachin, Lubiw, Anna, Maheshwari, Anil, Roy, Sasanka
A path from s to t on a polyhedral terrain is descending if the height of a point p never increases while we move p along the path from s to t. No efficient algorithm is known to find a shortest...
Linear-Space Algorithms for Distance Preserving Embedding ∗ (2008)
Tetsuo Asano, Prosenjit Bose, Paz Carmi, Anil Maheshwari, Chang Shu, Michiel Smid, ...
The distance preserving graph embedding problem is to embed vertices of a given weighted graph into points in 2-dimensional Euclidean space so that for each edge the distance between their...
ALGORITHMS FOR OPTIMAL OUTLIER REMOVAL ∗ (2008)
Rossen Atanassov, Prosenjit Bose, Mathieu Couture, Anil Maheshwari, Pat Morin, Michel Paquette, ...
Abstract. We consider the problem of removing c points from a set S of n points so that the remaining point set is optimal in some sense. Definitions of optimality we consider include having minimum...
Approximate Shortest Descent Path on a Terrain (2008)
Sasanka Roy, Sachin Lodha, Ip Das, Anil Maheshwari
A path from a point s to a point t on the surface of a polyhedral terrain is said to be descent if for every pair of points p = (x(p),y(p),z(p)) and q = (x(q),y(q),z(q)) on the path, if dist(s,p)...
We present I/O-efficient algorithms for computing optimal separator partitions of planar graphs. Our main result shows that, given a planar graph G with N vertices and an integer r> 0, a vertex...
On the falsepositive rate of Bloom filters (2008)
Prosenjit Bose, Hua Guo, Evangelos Kranakis, Anil Maheshwari, Pat Morin, Jason Morrison, ...
Abstract. Bloom filters are a randomized data structure for membership queries dating back to 1970. Bloom filters sometimes give erroneous answers to queries, called false positives. Bloom analyzed...
Abstract Sigma-Local Graphs (2008)
Prosenjit Bose, Sébastien Collette, Stefan Langerman, Anil Maheshwari, Pat Morin, Michiel Smid
We introduce and analyze σ-local graphs, based on a definition of locality by Erickson [9]. We present two algorithms to construct such graphs, for any real number σ> 1 and any set S of n...
Abstract Sigma-Local Graphs (2008)
Prosenjit Bose, Sébastien Collette, Stefan Langerman, Anil Maheshwari, Pat Morin, Michiel Smid
We introduce and analyze σ-local graphs, based on a definition of locality by Erickson [11]. We present two algorithms to construct such graphs, for any real number σ> 1 and any set S of n...
Anil Maheshwari, Pat Morin, Michel Paquette, Michiel Smid, Stefanie Wuhrer
We consider the problem of removing c points from a set S of n points so that the remaining point set is optimal in some sense. Definitions of optimality we consider include having minimum diameter,...
Spanners of Complete $k$-Partite Geometric Graphs (2007)
Bose, Prosenjit, Carmi, Paz, Couture, Mathieu, Maheshwari, Anil, Morin, Pat, Smid, Michiel
We address the following problem: Given a complete $k$-partite geometric graph $K$ whose vertex set is a set of $n$ points in $\mathbb{R}^d$, compute a spanner of $K$ that has a ``small'' stretch...
Anil Maheshwari, Andrzej Lingas, Andrzej Lingas
We present optimal parallel solutions to reporting paths between pairs of nodes in an n\Gammanode tree. Our algorithms are deterministic and designed to run on an exclusive read exclusive write...
Reducing I/O Complexity by Simulating Coarse Grained Parallel Algorithms (2007)
Exte Nd Ed, Frank Dehne, Wolfgang Dittrich, David Hutchinson, Anil Maheshwari
Frank Dehne 2 Wolfgang Dittrich 3 David Hutchinson 2;4 Anil Maheshwari 2;4 July 30, 1998 Abstract Block-wise access to data is a central theme in the design of efficient external memory (EM)...
I/O-Efficient Well-Separated Pair Decomposition and its Applications (Extended Abstract) (2007)
Satish Govindarajan, Tamas Lukovszki, Anil Maheshwari, Norbert Zeh
) Sathish Govindarajan 1 , Tamas Lukovszki 2 , Anil Maheshwari 3 , and Norbert Zeh 3 1 Duke University, gsat@cs.duke.edu 2 University of Paderborn, Heinz-Nixdorf-Institut, tamas@hni.upb.de 3 Carleton...
Fast Approximation of Sums of Distances (2007)
Prosenjit Bose, Anil Maheshwari, Pat Morin
We show how to preprocess a set S of n points in R d (d constant) using O(kn log d 1 n) time and space so that the sum of distances of points in S to a query point q can be approximated to within a...
On the falsepositive rate of Bloom filters (2007)
Prosenjit Bose, Hua Guo, Evangelos Kranakis, Anil Maheshwari, Pat Morin, Jason Morrison, ...
Abstract. Bloom filters are a randomized data structure for membership queries dating back to 1970. Bloom filters sometimes give erroneous answers to queries, called false positives. Bloom analyzed...
We describe two data structures that preprocess a set S of n points in R d (d constant) so that the sum of Euclidean distances of points in S to a query point q can be quickly approximated to within...
Translating a Regular Grid over a Point Set* (2007)
Marc Van Kret, Anil Maheshwari, Pat Morin, Pat Morin, Jason Morrison, Jason Morrison
We consider the problem of translating a (finite or infinite) squoxe grid G over a set S of n points in the plane in order to maximize some objective function. We say that a grid cell is k-occupied...
Callahan and Kosaraju [7] introduced the well separated pair decomposition (WSPD) data structure as a mechanism for solving a number of problems on point sets in d-dimensional space. We present an...
Frank Dehne, Wolfgang Dittrich, David Hutchinson, Anil Maheshwari
Block-wise access to data is a central theme in the design of efficient external memory (EM) algorithms. A second important issue, when more than one disk is present, is fully parallel disk I/O. In...
I/O-Ecient Algorithms for Graphs of Bounded Treewidth (2007)
We present I/O-ecient algorithms for the single source shortest path problem and NP-hard problems on graphs of bounded treewidth. The main step in these algorithms is a method to compute a...
Lyudmil Aleksandrov, Mark Lanthier, Anil Maheshwari
Shortest path problems are among the fundamental problems studied in computational geometry and other areas such as graph algorithms, geographical information systems (GIS) and robotics. Due to their...
Lyudmil Aleksandrov, Mark Lanthier, Anil Maheshwari
Abstract. Let P be a simple polyhedron, possibly non-convex, whose boundary is composed of n triangular faces, and in which each face has an associated positive weight. The cost of travel through...
Approximating Shortest Paths on Weighted Polyhedral Surfaces (2007)
Mark Lanthier, Anil Maheshwari, Jörg-Rüdiger Sack
Shortest path problems are among the... In this paper we propose several simple and practical algorithms (schemes) to compute an approximated weighted shortest path Π'(s, t) points s and...
Approximating Geometric Bottleneck Shortest Paths (2007)
Prosenjit Bose, Anil Maheshwari, Giri Narasimhan, Michiel Smid, Norbert Zeh
In a geometric bottleneck shortest path problem, we are given a set S of n points in the plane, and want to answer queries of the following type: Given two points p and q of S and a real number L,...
A Framework for Multiresolution Modelling (2007)
Anil Maheshwari, Pat Morin, Jörg-Rüdiger Sack
Introduction The subject of multiresolution surface modelling has received considerable attention from a number of fields, including computational geometry, geographic information systems, and...
Geometric Spanners With Small Chromatic Number (2007)
Bose, Prosenjit, Carmi, Paz, Couture, Mathieu, Maheshwari, Anil, Smid, Michiel, Zeh, Norbert
Given an integer $k \geq 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...
Geometric spanners with small chromatic number (2007)
Prosenjit Bose, Paz Carmi, Mathieu Couture, Anil Maheshwari, Michiel Smid, Norbert Zeh
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...
Geometric Spanners With (2007)
Small Chromatic Number, Anil Maheshwari, Michiel Smid, Norbert Zeh
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, a t(k)-spanner for P exists that has O(|P |) edges and...
An improved algorithm for Hausdorff Voronoi diagram for non-crossing sets ∗†‡ (2006)
Frank Dehne, Anil Maheshwari, Ryan Taylor
We present an improved algorithm for building a Hausdorff Voronoi diagram (HVD) for non-crossing objects. Our algorithm runs in O(nlog 4 n) time, where n is the total number of points defining the...
Submitted by Phuong Dao, 100337321 (2006)
Supervised Dr, Anil Maheshwari
This report describes the study and implementation of Scapegoat trees, weight and loosely-height-balanced binary search trees, first proposed in the paper:”Scapegoat Trees”[Igal Galperin and...
Approximate shortest path queries on weighted polyhedral surfaces (2006)
Lyudmil Aleksandrov, Hristo N. Djidjev, Hua Guo, Anil Maheshwari, Doron Nussbaum, Jörg-rüdiger Sack
We consider the classical geometric problem of determining shortest paths between pairs of points lying on a weighted polyhedral surface P consisting of n triangular faces. We present query...
Approximating Geometric Bottleneck Shortest Paths (2004)
Prosenjit Bose, Anil Maheshwari, Giri Narasimhan, Michiel Smid, Norbert Zeh
In a geometric bottleneck shortest path problem, we are given a set S of n points in the plane, and want to answer queries of the following type: Given two points p and q of S and a real number L,...
Translating a regular grid over a point set (2003)
Marc Van Kreveld, Anil Maheshwari, Pat Morin, Jason Morrison
We consider the problem of translating a ( nite or innite) square grid G over a set S of n points in the plane in order to maximize some objective function. We say that a grid cell is k-occupied if...
Translating a regular grid over a point set (2003)
Marc Van Kreveld, Anil Maheshwari, Pat Morin, Jason Morrison
We consider the problem of translating a ( nite or innite) square grid G over a set S of n points in the plane in order to maximize some objective function. We say that a grid cell is k-occupied if...
Translating a regular grid over a point set (2003)
Marc Van Kreveld, Anil Maheshwari, Pat Morin, Jason Morrison
We consider the problem of translating a ( nite or innite) square grid G over a set S of n points in the plane in order to maximize some objective function. We say that a grid cell is k-occupied if...
Translating a regular grid over a point set (2003)
Anil Maheshwari, Pat Morin, Jason Morrison
We consider the problem of translating a (finite or infinite) square grid G over a set S of n points in the plane in order to maximize some objective function. We say that a grid cell is k-occupied...
Translating a Regular Grid over a Point Set (2002)
Bose, Prosenjit, Kreveld, Marc Van, Maheshwari, Anil, Morin, Pat, Morrison, Jason
Fast approximations for sums of distances, clustering and the Fermat-Weber problem (2002)
Carleton University
Fast approximations for sums of distances, clustering and the Fermat-Weber problem (2002)
Prosenjit Bose, Anil Maheshwari, Pat Morin
We describe two data structures that preprocess a set S of n points in R d (d constant) so that the sum of Euclidean distances of points in S to a query point q can be quickly approximated to within...
Fast approximations for sums of distances, clustering and the Fermat-Weber problem (2002)
Prosenjit Bose, Anil Maheshwari, Pat Morin
We describe two data structures that preprocess a set S of n points in R
Bulk Synchronous Parallel Algorithms for the External Memory Model (2002)
Frank Dehne, Wolfgang Dittrich, David Hutchinson, Anil Maheshwari, Bosch Telecom Gmbh
Blockwise access to data is a central theme in the design of efficient external memory (EM) algorithms. A second important issue, when more than one disk is present, is fully parallel disk I/O. In...
On Reverse Nearest Neighbor Queries (2002)
Extended Anil, Anil Maheshwari, Norbert Zeh
In this paper, we discuss static and dynamic data structures for answering reverse nearest neighbor queries in two dimensions.
I/O-efficient algorithms for bounded treewidth graphs (2001)
We present an I/O-efficient algorithm for the single source shortest path (SSSP) problem for graphs of bounded treewidth. For sparse graphs in general SSSP seems to be extremely hard to solve. We...
I/O-efficient shortest path queries in geometric spanners (2001)
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]...
I/O-efficient batched range counting and its applications to proximity problems (2001)
Abstract. We present an algorithm to answer a set Q of range counting queries over a point set P in d dimensions. The algorithm takes O sort(jP j + jQj) + (jP j+jQj)(jP j) DB log d 1 M=B
I/O-efficient algorithms for bounded treewidth graphs (2001)
We present an I/O-efficient algorithm for the single source shortest path (SSSP) problem for graphs of bounded treewidth. For sparse graphs in general SSSP seems to be extremely hard to solve. We...
I/O-efficient shortest path queries in geometric spanners (2001)
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]...
I/O-Optimal Algorithms for Outerplanar Graphs (2001)
We present linear-I/O algorithms for fundamental graph problems on embedded outerplanar graphs. We show that breadth-first search, depth-first search, single-source shortest paths, triangulation, and...
I/O-efficient well-separated pair decomposition and its applications (2000)
Sathish Govindarajan, Tamás Lukovszki, Anil Maheshwari, Norbert Zeh
Abstract. We present an external memory algorithm to compute a well-separated pair decomposition (WSPD) of a given point set P in £ d in O ¤ sort ¤ N¥¦ ¥ I/Os using O ¤ N § B ¥ blocks of...
I/O-efficient well-separated pair decomposition and its applications (2000)
Sathish Govindarajan, Anil Maheshwari, Norbert Zeh
Data sets of many modern applications are too large to fit into main memory, and must reside on disk. It has been observed that the Input/Output (I/O) communication between internal memory and disk...
I/O-efficient well-separated pair decomposition and its applications (2000)
Sathish Govindarajan, Tamás Lukovszki, Anil Maheshwari, Norbert Zeh
Abstract. We present an external memory algorithm to compute a well-separated pair decomposition (WSPD) of a given point set P in £ d in O ¤ sort ¤ N¥¦ ¥ I/Os using O ¤ N § B ¥ blocks of...
I/O-efficient well-separated pair decomposition and its applications (2000)
Sathish Govindarajan, Tamás Lukovszki, Anil Maheshwari, Norbert Zeh
Abstract. We present an external memory algorithm to compute a well-separated pair decomposition (WSPD) of a given point set P in £ d in O ¤ sort ¤ N¥¦ ¥ I/Os using O ¤ N § B ¥ blocks of...
External memory algorithms for outerplanar graphs (1999)
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 a 2
Reducing i/o complexity by simulating coarse grained parallel algorithms (1999)
Frank Dehne, David Hutchinson, Anil Maheshwari, Wolfgang Dittrich
Block-wise access to data is a central theme in the design of efficient external memory (EM) algorithms. A second important issue, when more than one disk is present, is fully parallel disk I/O. In...
Reducing i/o complexity by simulating coarse grained parallel algorithms (1999)
Frank Dehne, David Hutchinson, Anil Maheshwari, Wolfgang Dittrich
Block-wise access to data is a central theme in the design of efficient external memory (EM) algorithms. A second important issue, when more than one disk is present, is fully parallel disk I/O. In...
Shortest Anisotropic Paths on Terrains (1999)
Mark Lanthier, Anil Maheshwari
Abstract. We discuss the problem of computing shortest an-isotropic paths on terrains. Anisotropic path costs take into account the length of the path traveled, possibly weighted, and the direction...
An External-Memory Data Structure for Shortest Path Queries (1999)
David Hutchinson, Anil Maheshwari, Norbert Zeh, N That Uses
In this paper, we present results related to satisfying shortest path queries on a planar graph stored in external memory. N denotes the total number of vertices and edges in the graph and sort(N)...
Reducing I/O Complexity by Simulating Coarse Grained Parallel Algorithms (1999)
Frank Dehne, David Hutchinson, Anil Maheshwari, Wolfgang Dittrich
Block-wise access to data is a central theme in the design of efficient external memory (EM) algorithms. A second important issue, when more than one disk is present, is fully parallel disk I/O. In...
Algorithms for packing two circles in a convex polygon (1998)
Jurek Czyzowicz, Evangelos Kranakis, Anil Maheshwari
Abstract. We consider algorithms for packing two circles in a given n-vertex convex polygon. The rst algorithm outputs a pair of equal non-overlapping circles of maximum radius and has running time...
Blocking in Parallel Multisearch Problems (Extended Abstract) (1998)
Wolfgang Dittrich, David Hutchinson, Anil Maheshwari
) Wolfgang Dittrich Bosch Telecom GmbH, UC-ON/ERS Gerberstrae 33 71522 Backnang, Germany Wolfgang.Dittrich@bk.bosch.de David Hutchinson y School of Computer Science Carleton University Ottawa, Canada...
Progressive TINs: Algorithms and applications (1997)
Anil Maheshwari, Pat Morin, Jorg-rudiger Sack
Transmission of geographic data over the Internet, rendering at different resolutions /levels of detail, or processing at unnecessarily fine detail pose interesting challenges and opportunities. In...
Efficient computation of implicit representations of sparse graphs (1997)
Srinivasa R. Arikati, Anil Maheshwari, Christos D. Zaroliagis
The problem of finding an implicit representation for a graph such that vertex adjacency can be tested quickly is fundamental to all graph algorithms. In particular, it is possible to represent...
Progressive TINs: Algorithms and Applications (1997)
Anil Maheshwari, Pat Morin, Jörg-Rüdiger Sack
Transmission of geographic data over the Internet, rendering at different resolutions/levels of detail, or processing at unnecessarily fine detail pose interesting challenges and opportunities. In...
Early Experiences in Implementing the Buffer Tree (1997)
David Hutchinson, Anil Maheshwari, Jörg-Rüdiger Sack, Radu Velicescu
Computer processing speeds are increasing rapidly due to the evolution of faster chips, parallel processing of data, and more efficient software. Users today have access to an unprecedented amount of...
Approximating Weighted Shortest Paths on Polyhedral Surfaces (1997)
Mark Lanthier, Anil Maheshwari, Jörg-Rüdiger Sack
Consider a simple polyhedron P, possibly non-convex, composed of n triangular regions (faces), in which each region has an associated positive weight. The cost of travel through each region is the...
Approximating Weighted Shortest Paths on Polyhedral Surfaces (1997)
Mark Lanthier, Anil Maheshwari, Jörg-Rüdiger Sack
Introduction Shortest path problems are among the fundamental problems studied in computational geometry. In this video, we consider the problem of computing a shortest cost path between two points s...
Approximating Weighted Shortest Paths on Polyhedral Surfaces (1996)
Mark Lanthier, Anil Maheshwari, Jörg-Rüdiger Sack
Consider a simple polyhedron P, possibly non-convex, composed of n triangular regions (faces), each assigned a positive weight indicating the cost of travel in that region. We present and...
$_N$$_C-$ Algorithms for Minimum Link Path and Related Problems (1995)
Chandru, Vijay, Ghosh, Subir Kumar, Maheshwari, Anil, Rajan, VT, Saluja, Sanjeev
The link metric, defined on a constrained region R of the plane, sets the distance between a pair of points in R to equal the minimum number of line segments or links that are needed to construct a...
$_N$$_C-$ Algorithms for Minimum Link Path and Related Problems (1995)
Chandru, Vijay, Ghosh, Subir Kumar, Maheshwari, Anil, Rajan, VT, Saluja, Sanjeev
The link metric, defined on a constrained region R of the plane, sets the distance between a pair of points in R to equal the minimum number of line segments or links that are needed to construct a...
Stage-Graph Representations (1995)
Evangelos Kranakis, Danny Krizanc, Anil Maheshwari, Marc Noy, Jörg-Rüdiger Sack, Jorge Urrutia
We consider graph applications of the well-known paradigm "killing two birds with one stone". In the plane, this gives rise to a stage graph as follows: vertices are the points, and fu; vg...
Ray Shooting from Convex Ranges (1995)
Evangelos Kranakis, Danny Krizanc, Anil Maheshwari, Jörg-Rüdiger Sack, Jorge Urrutia
We consider geometric and graph-theoretic aspects of the well-known paradigm "killing two birds with one stone". Consider that we have a set X of n-points in space and a compact plane...
Planar Stage Graphs: Characterizations And Applications (1995)
Frank Bauernöppel, Evangelos Kranakis, Danny Krizanc, Anil Maheshwari, Jörg-Rüdiger Sack, Jorge Urrutia
We consider combinatorial and algorithmic aspects of the well-known paradigm "killing two birds with one stone". We define a stage graph as follows: vertices are the points from a planar...
An Improved Maximum Matching Algorithm in a Permutation Graph (1995)
Frank Bauernöppel, Evangelos Kranakis, Danny Krizanc, Anil Maheshwari, Jörg-Rüdiger Sack, Jorge Urrutia
Introduction We present an O(n log 2 n) time algorithm for computing a maximum matching in a permutation graph on n-vertices. Our results are based on the algorithm of [12] for a two processor...
Efficient Computation of Implicit Representations of Sparse Graphs (1995)
Srinivasa R. Arikati, Anil Maheshwari, Christos D. Zaroliagis
The problem of finding an implicit representation for a graph such that vertex adjacency can be tested quickly is fundamental to all graph algorithms. In particular, it is possible to represent...
Efficient Computation of Compact Representations of Sparse Graphs (1994)
Srinivasa Rao Arikati, Anil Maheshwari, Srinivasa Rao, Arikati Anil Maheshwari, Christos Zaroliagis
Sparse graphs (e.g. trees, planar graphs, relative neighborhood graphs) are among the commonly used data-structures in computational geometry. The problem of finding a compact representation for...
Optimal Parallel Algorithms for Rectilinear Link Distance Problems (1992)
Andrzej Lingas, Anil Maheshwari, Jörg-Rüdiger Sack
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...
Polygon Cutting: Revisited Prosenjit Bose
Jurek Czyzowicz, Evangelos Kranakis, Danny Krizanc, Anil Maheshwari
Abstract. Given a simple polygon P on n vertices v0; v1; : : : ; vn 1 with each edge assigned a non-negative weight w i, we show how to compute in O(n) time a segment v i b (where b is a point on the...