Pankaj K. Agarwal

I/O-Efficient Structures for Orthogonal Range-Max and Stabbing-Max Queries (2009)

Abstract. We present simple, fully dynamic and kinetic data structures, which are variants of a dynamic two-dimensional range tree, for maintaining the closest pair and all nearest neighbors for a...

Abstract Extreme Elevation on a 2-Manifold (2009)

Abstract. We develop several linear or near-linear space and I/Oefficient dynamic data structures for orthogonal range-max queries and stabbing-max queries. Given a set of N weighted points in d, the...

Pankaj K. Agarwal, Herbert Edelsbrunner, John Harer

Given a smoothly embedded 2-manifold in ¤¦ ¥ , we define the elevation of a point as the height difference to a canonically defined second point on the same manifold. Our definition is invariant...

Extreme Elevation on a 2-Manifold \Lambda (2009)

Pankaj K. Agarwal, Herbert Edelsbrunnerz, John Harerx, Yusu Wangy

Abstract Given a smoothly embedded 2-manifold in R 3, we define the elevation of a point as the height difference to a canonicallydefined second point on the same manifold. Our definition is...

References (2009)

Roberto Tamassia, Pankaj K. Agarwal, Nancy Amato, Danny Z. Chen, David Dobkin

Patrick R. Morin 1 Outline of Proposed Research Activities The proposed research will be in the area of applied algorithms in both the sequential and parallel domains. The focus of this work will be...

Abstract Computing the Writhing Number of a Polygonal Knot (2008)

Pankaj K. Agarwal, Lars Arge

The writhing number measures the global geometry of a closed space curve or knot. We show that this measure is related to the average winding number of its Gauss map. Using this relationship, we give...

ABSTRACT (2008)

A terrain M is the graph of a bivariate function. We assume that M is represented as a triangulated surface with N vertices. A contour (or isoline) of M is a connected component of a level set of M....

A two-dimensional kinetic triangulation with near-quadratic topological changes (2008)

Pankaj K. Agarwal, Yusu Wang, Hai Yu

Abstract A triangulation of a set S of points in the plane is a subdivision of the convex hull of S intotriangles whose vertices are points of S. Given a set S of n points in R2, each moving...

Two randomized incremental algorithms for planar arrangements, with a twist (2008)

Pankaj K. Agarwal, Sariel Har-Peled

We present two results related to randomized incremental construction of planar arrangements: • An algorithm for computing the union of triangles in the plane in a quasi output- sensitive time. •...

General Terms (2008)

Pankaj K. Agarwal, Lars Arge, Andrew Danner, Bryan Holl

We develop cache-oblivious data structures for orthogonal range searching, the problem of finding all T points in a set of N points in Ê d lying in a query hyper-rectangle. Cacheoblivious data...

and Problem Complexity]: Nonnumerical Algorithms and (2008)

Independent Set of Intersection Graphs ofConvex Objects in 2D \Lambda (2008)

We present a near-quadratic algorithm for computing the center region of a set of n points in three dimensions. This is nearly tight in the worst case since the center region can have Ω(n 2)...

Geometric Approximation Using Coresets 1 Shape Fitting: Set of ¡points in¢�� (2008)

Abstract The intersection graph of a set of geometric objects is defined as a graph G = (S; E) inwhich there is an edge between two nodes si; sj 2 S if si " sj 6 =;. The problem of...

I/O-Efficient Structures for Orthogonal Range-Max and Stabbing-Max Queries (2008)

Diametral pair can change � times � ¡ £ Kinetic data structure with events � ✫ Can we maintain the approximate diameter of more efficiently? Is there a small coreset s.t. �

I/O-Efficient Structures for Orthogonal Range-Max and Stabbing-Max Queries (2008)

Abstract. We develop several linear or near-linear space and I/Oefficient dynamic data structures for orthogonal range-max queries and stabbing-max queries. Given a set of N weighted points in R d,...

Contemporary Mathematics State of the Union (of Geometric Objects) (2008)

Abstract. We develop several linear or near-linear space and I/Oefficient dynamic data structures for orthogonal range-max queries and stabbing-max queries. Given a set of N weighted points in R d,...

Pankaj K. Agarwal, János Pach, Micha Sharir

ABSTRACT. Let C be a set of geometric objects in R d. The combinatorial complexity of the union of C is the total number of faces of all dimensions on its boundary. We survey the known upper bounds...

Scalable Continuous Query Processing byTracking Hotspots* (2008)

Pankaj K. Agarwal, Junyi Xie, Jun Yang, Computer Science

ABSTRACT This paper considers the problem of scalably processing a largenumber of continuous queries. We propose a flexible framework with novel data structures and algorithms for group-processing...

TerraStream: From elevation data to watershed hierarchies (2008)

Andrew Danner, Pankaj K. Agarwal, Ke Yi, Lars Arge

We consider the problem of extracting a river network and a watershed hierarchy from a terrain given as a set of irregularly spaced points. We describe TerraStream, a “pipelined ” solution that...

From Data Reverence to Data Relevance: Model-Mediated Wireless Sensing of the Physical Environment (2008)

Paul G. Flikkema, Pankaj K. Agarwal, James S. Clark, Carla Ellis, Alan Gelf, Kamesh Munagala

Abstract. Wireless sensor networks can be viewed as the integration of three subsystems: a low-impact in situ data acquisition and collection system, a system for inference of process models from...

Polytechnic University AND (2008)

Pankaj K. Agarwal, Boris Aronov, Vladlen Koltun

Abstract. A closed solid body separates one point set from another if it contains the former and the closure of its complement contains the latter. We present a near-linear algorithm for deciding...

An Efficient Algorithm for 2D Euclidean 2-Center with Outliers (2008)

Agarwal, Pankaj K., Phillips, Jeff M.

For a set P of n points in R^2, the Euclidean 2-center problem computes a pair of congruent disks of the minimal radius that cover P. We extend this to the (2,k)-center problem where we compute the...

138 BIBLIOGRAPHY (2008)

Pankaj K. Agarwal, Its Relatives In, B. Chazelle, J. E. Goodman, R. Pollack, Advances In Discrete, ...

[1] P. K. Agarwal. Partitioning arrangements of lines II: Applications. Discrete & Computational

Associate Editors (2008)

Dimitris Papadias, Yufei Tao, Jun Zhang, Nikos Mamoulis, Qiongmao Shen, Jimeng Sun, ...

VLDB Conference......................................................................� � � ÓÚ�Ö

Abstract (2008)

Pankaj K. Agarwal, Ferran Hurtado, Godfried T. Toussaint, Joan Trias

It is well known that one can always polygonize a set ¥ of ¦¨§� © points in the plane (not all on a line), i.e., construct a simple polygon � whose vertices are precisely the given points in...

36 RANGE SEARCHING (2008)

A Framework for Index Bulk Loading and (2008)

Range searching is one of the central problems in computational geometry, because it arises in many applications and a variety of geometric problems can be formulated as range-searching problems. A...

Pankaj K. Agarwal, Lars Arge, Octavian Procopiuc, Jeffrey Scott Vitter

Abstract. In this paper we investigate automated methods for externalizing internal memory data structures. We consider a class of balanced trees that we call weight-balanced partitioning trees (or...

ABSTRACT Scalable Continuous Query Processing by Tracking Hotspots ∗ (2008)

Pankaj K. Agarwal, Roel Apfelbaum

This paper considers the problem of scalably processing a large number of continuous queries. We propose a flexible framework with novel data structures and algorithms for group-processing and...

We consider the problem of bounding the maximum possible number ¡£¢£ ¤ ¥§¦©¨� � � of-simplices that are spanned by a set of ¨ points � ¥ in and are similar to a given simplex. We...

Downloaded from (2008)

Pankaj K Agarwal, Julien Basch, Leonidas J Guibas, John Hershberger, Li Zhang, Pankaj K. Agarwal, ...

We present kinetic data structures for detecting collisions between a set of polygons that are moving continuously. Unlike classical collision detection methods that rely on bounding volume...

Abstract Extreme Elevation on a 2-Manifold (2008)

Pankaj K. Agarwal, Herbert Edelsbrunner, John Harer

Given a smoothly embedded 2-manifold in ¤¦ ¥ , we define the elevation of a point as the height difference to a canonically defined second point on the same manifold. Our definition is invariant...

• Discretization of the 8100 (2008)

Sathish Govindarajan, Sukhendu Chakraborty, Pankaj K. Agarwal, Michael C. Dietze, James S. Clark, Light Model

Predicting understory light on a landscape Efficient simulations using approximation algorithms Understanding inter individual interactions Ecological forecasting

A scalable algorithm for dispersing population (2008)

Sathish Govindarajan, Mike Dietze, James S. Clark, Pankaj K. Agarwal

A two-dimensional kinetic triangulation with near-quadratic topological changes (2008)

Pankaj K. Agarwal, Yusu Wang, Hai Yu

Given a set of n points S in the plane, a triangulation of S is a subdivision of the convex hull into triangles whose vertices are from S. In the kinetic setting, the input point set is replaced by a...

A two-dimensional kinetic triangulation with near-quadratic topological changes (2008)

Pankaj K. Agarwal, Yusu Wang, Hai Yu

A triangulation of a set S of points in the plane is a subdivision of the convex hull of S into triangles whose vertices are points of S. Given a set S of n points in R 2, each moving independently,...

General Terms (2008)

Pankaj K. Agarwal, Lars Arge, Andrew Danner, Bryan Holl

We develop cache-oblivious data structures for orthogonal range searching, the problem of finding all T points in a set of N points in Ê d lying in a query hyper-rectangle. Cacheoblivious data...

Abstract Computing the Writhing Number of a Polygonal Knot (2008)

Pankaj K. Agarwal, Herbert Edelsbrunner, Yusu Wang

The writhing number measures the global geometry of a closed space curve or knot. We show that this measure is related to the average winding number of its Gauss map. Using this relationship, we give...

Segmenting Object Space by Geometric Reference Structures (2008)

Pankaj K. Agarwal, David Brady

A model for segmentation of an object space by an array of binary, radiation-field sensors and geometric reference structures is described. Given a family of binary, radiation-field sensors and a...

RESEARCH EXPERIENCE (2008)

Graduate Advisors, John L. Harer, Pankaj K. Agarwal

Shape classification via persistent homology.

I/O-Efficient Construction of Constrained (2008)

Delaunay Triangulations, Pankaj K. Agarwal, Lars Arge, Ke Yi

Abstract. In this paper, we designed and implemented an I/O-efficient algorithm for constructing constrained Delaunay triangulations. If the number of constraining segments is smaller than the memory...

CHAPTER ELEVEN A Simple and Efficient Algorithm for High-Quality Line Labeling (2008)

Alexander Wolff, Marc Kreveld, Tycho Strijk, Pankaj K. Agarwal

The interest in algorithms that automatically place labels on maps, graphs, or diagrams has increased with the advance in type-setting technology and the amount of information to be visualized....

Abstract Cylindrical Static and Kinetic Binary Space Partitions (2008)

Pankaj K. Agarwal, Leonidas J. Guibas

We describe the rst known algorithm for e ciently maintaining a Binary Space Partition (BSP) for n continuously moving segments in the plane. Under reasonable assumptions on the motion, we show that...

Kinetic Medians and ��-Trees (2008)

Pankaj K. Agarwal, Leonidas J. Guibas

Abstract. We propose algorithms for maintaining two variants of ��-trees of a set of moving points in the plane. A pseudo ��-tree allows the number of points stored in the two children to...

Pankaj K. Agarwal, Boris Aronov, Vladlen Koltun, Micha Sharir

Abstract. Let B be a set of n unit balls in R 3. We show that the combinatorial complexity of the space of lines in R 3 that avoid all the balls of B is O(n 3+ε), for any ε>0. This result has...

ABSTRACT Computing the Volume of the Union of Cubes ∗ (2008)

ABSTRACT Algorithms for Center and Tverberg Points ∗ (2008)

Let C be a set of n axis-aligned cubes in R 3, and let U(C) denote the union of C. We present an algorithm that can compute the volume of U(C) in time O(n 4/3 log n). The previously best known...

ABSTRACT Guarding a Terrain by Two Watchtowers ∗ (2008)

We present a near-quadratic algorithm for computing the center region of a set of n points in three dimensions. This is nearly tight in the worst case since the center region can have Ω(n 2)...

Pankaj K. Agarwal, Sergey Bereg, Ovidiu Daescu, Haim Kaplan, Simeon Ntafos, Binhai Zhu

Given a polyhedral terrain T with n vertices, the two-watchtower problem for T calls for finding two vertical segments, called watchtowers, of smallest common height, whose bottom endpoints (bases)...

Computing maximally separated sets in the plane and independent sets in the intersection graph of unit graphs (2008)

Pankaj K. Agarwal, Mark Overmars, Micha Sharir

Let S be a set of n points in R2. Given an integer 1 ≤ k ≤ n, we wish to find a maximally separated subset I ⊆ S of size k; this is a subset for which the minimum among the � � k 2 pairwise...

Approximation Algorithms for �-Line Center � (2008)

Pankaj K. Agarwal, Cecilia M. Procopiuc, Kasturi R. Varadarajan

Abstract. Given a set È of Ò points in Ê � and an integer � �,letÛ £ denote the minimum value so that È can be covered by � cylinders of radius at most Û £. We describe an algorithm...

Approximating extent measures of points (2008)

Pankaj K. Agarwal, Sariel Har-peled, Kasturi R. Varadarajan

We present a general technique for approximating various descriptors of the extent of a set P of n points in R d. For a given extent measure µ and a parameter ε> 0, it computes in time O(n +...

COMPUTING MAXIMALLY SEPARATED SETS IN THE PLANE ∗ (2008)

Pankaj K. Agarwal, Mark Overmars, Micha Sharir

Abstract. Let S be a set of n points in R2. Given an integer 1 ≤ k ≤ n, we wish to find a maximally separated subset I ⊆ S of size k; this is a subset for which the minimum among the �k � 2...

Computing the detour and spanning ratio of paths, trees and cycles in 2D and 3D (2008)

Pankaj K. Agarwal, Rolf Klein, Christian Knauer, Stefan Langerman, Pat Morin, Micha Sharir, ...

The detour and spanning ratio of a graph � embedded in �� measure how well � approximates Euclidean space and the complete Euclidean graph, respectively. In this paper we describe...

On the complexity of many faces in arrangements of pseudo-segments and of circles (2008)

Efficient Algorithms, Bichromatic Separability, Pankaj K. Agarwal, Boris Aronov, Vladlen Koltun

We obtain improved bounds on the complexity of m distinct faces in an arrangement of n pseudo-segments, n circles, or n unit circles. The bounds are worst-case optimal for unit circles; they are also...

\Lambda (2008)

z

Faster Algorithms for Optimal Multiple Sequence Alignment based on Pairwise Comparisons ∗ (2008)

Pankaj K. Agarwal, Yonatan Bilu, Rachel Kolodny

Multiple Sequence Alignment (MSA) is one of the most fundamental problems in computational molecular biology. The running time of the best known scheme for finding an optimal alignment, based on...

Nonnumerical Algorithms and Problems (2008)

Pankaj K. Agarwal, Lars Arge, Andrew Danner, Bryan Holl

We develop cache-oblivious data structures for orthogonal range searching, the problem of finding all T points in a set of N points in Ê d lying in a query hyper-rectangle. Cacheoblivious data...

Efficient Generation of k-Directional Assembly Sequences (2008)

Pankaj K. Agarwal, Mark De Berg, Dan Halperin, Micha Sharir

Let S be a collection of n rigid bodies in 3-space, and let D be a set of k directions in 3-space, where k is a small constant. A k-directional assembly sequence for S, with respect to D, is a linear...

State of the Union (of geometric objects) (2008)

Pach, János, Agarwal, Pankaj K., Sharir, Micha

Untangling Triangulations through Local Explorations * (2008)

Pankaj K. Agarwal, Bardia Sadri, Hai Yu

Abstract The problem of maintaining a valid mesh (triangulation) within a certain domain that de-forms over time arises in many applications. During a period for which the underlying mesh

Untangling Triangulations through Local Explorations ∗ (2008)

Pankaj K. Agarwal, Bardia Sadri, Hai Yu

The problem of maintaining a valid mesh (triangulation) within a certain domain that deforms over time arises in many applications. During a period for which the underlying mesh topology remains...

A scalable algorithm for dispersing population (2008)

Govindarajan, Sathish, Dietze, Michael C., Agarwal, Pankaj K., Clark, James S.

Models of forest ecosystems are needed to understand how climate and land-use change can impact biodiversity. In this paper we describe an ecological dispersal model developed for the specific case...

AND (2008)

Pankaj K. Agarwal, Eth Zürich

Abstract. Given a set S of n points in R 3, a point x in R 3 is called center point of S if every closed halfspace whose bounding hyperplane passes through x contains at least ⌈n/4 ⌉ points from...

Constructing Binary Space Partitions for Orthogonal Rectangles in Practice (2007)

T. M. Murali, Pankaj K. Agarwal, Jeffrey Scott Vitter

. In this paper, we develop a simple technique for constructing a Binary Space Partition (BSP) for a set of orthogonal rectangles in R 3 . Our algorithm has the novel feature that it tunes its...

I/O-Efficient Dynamic Point Location in Monotone Planar Subdivisions (Extended Abstract) (2007)

Pankaj K. Agarwal, Lars Arge, Gerth Stølting Brodal, Jeffrey S. Vitter

) Pankaj K. Agarwal Lars Arge y Gerth Stølting Brodal z Jeffrey S. Vitter x Abstract We present an efficient external-memory dynamic data structure for point location in monotone planar...

Occlusion Culling for Fast Walkthrough in Urban Areas (2007)

Pankaj K. Agarwal, Sariel Har-peled, Yusu Wang

Figure 1: Demonstration of our algorithm on a Manhattan-suburb city model with 27,400 polygons used in our walkthrough applications. (a) is a bird-eye view of the city model from some position. (b)...

x (2007)

Pankaj K. Agarwal, Lars Arge, Jeff Erickson, Paolo G. Franciosa, Jeffrey Scott Vitter

We show how to preprocess a set S of points in R d to get an external memory data structure that efficiently supports linear-constraint queries. Each query is in the form of a linear constraint a...

Acknowledgments (2007)

Have Been Very, T. M. Murali, T. M. Murali, Jeffrey Scott Vitter, Pankaj K. Agarwal, John F. Hughes

this paper, we consider the following problem:

Indexing Moving Points (2007)

Exte Nd Ed, Pankaj K. Agarwal, Lars Arge, Je Erickson Z

) Pankaj K. Agarwal Lars Arge y Jeff Erickson z Submitted to 19th ACM Symposium on Principles of Database Systems. November 8, 1999 Abstract We propose three indexing schemes for storing a set S of N...

R-Linear Decision Tree, (2007)

Models Of Computation, Comput Geom, N. Alon, B. Aronov, Pankaj K. Agarwal, Pankaj K. Agarwal

ize, 2, 9, 31--32 Overmars, Mark, 27, 91 Pach, J'anos, 7, 106 Pal'asti, Ilona, 22 partition graph, 81 as a range searching data structure, 107 level of node in, 82 polyhedral, 102 primal...

1 d (2007)

Pankaj K. Agarwal, Jeff Erickson

. 1. Introduction HW Cl, Cl2 CS Pankaj K. Agarwal and Jeff Erickson Geometric Range Searching and Its Relatives Contemporary Mathematics c 0000 (copyright holder) Mathematics Subject Classification....

Discrete And Computational Geometry: Ten Years Later (2007)

Bernard Chazelle, J Anos Pach, Pankaj K. Agarwal, Nina Amenta

.77> O(f 2 ) vertices. The (incorrect) conjecture of the title is that o(f 2 ) of these vertices can appear on the outer boundary of a projection to the plane (a "shadow"). The video...

Efficient Generation of (2007)

Proc Th, Pankaj K. Agarwal, Mark De Berg, Dan Halperin, Micha Sharir

Let S be a collection of n rigid bodies in 3-space, and let D be a set of k directions in 3-space, where k is a small constant. A k-directional assembly sequence for S, with respect to D, is a linear...

Motion Planning for a Steering-Constrained Point Robot through Moderate Obstacles (2007)

Pankaj K. Agarwal, Prabhakar Raghavan, Hisao Tamaki

Most mobile robots use steering mechanisms to guide their motion. Such mechanisms have stops that constrain the rate at which the robot can change its direction. We study a point robot in the plane...

Efficient Generation of (2007)

To Appear, Pankaj K. Agarwal, Mark De Berg, Dan Halperin, Micha Sharir

Let S be a collection of n rigid bodies in 3-space, and let D be a set of k directions in 3-space, where k is a small constant. A k-directional assembly sequence for S, with respect to D, is a linear...

z (2007)

Pankaj K. Agarwal, Leonidas J. Guibas, T. M. Murali, Jeffrey Scott Vitter

We describe the first known algorithm for efficiently maintaining a Binary Space Partition (BSP) for n continuously moving segments in the plane. Under reasonable assumptions on the motion, we show...

References (2007)

Roberto Tamassia, Pankaj K. Agarwal, Nancy Amato, Danny Z. Chen, David Dobkin, ...

The proposed research will be in the area of applied algorithms in both the sequential and parallel domains. The focus of this work will be on the design and testing of realistic algorithms for...

Segments (2007)

Otfried Schwarzkopf, Otfried Schwarzkopf, Pankaj K. Agarwal, Pankaj K. Agarwal, Pankaj K. Agarwal

y Jir'i Matousek z Otfried Schwarzkopf x We present randomized algorithms for computing many faces in an arrangement of lines or of segments in the plane, which are considerably simpler and...

x Submitted to Journal of Computer and System Sciences (2007)

Pankaj K. Agarwal, Lars Arge, Jeff Erickson

We propose three indexing schemes for storing a set S of N points in the plane, each moving along a linear trajectory, so that a query of the following form can be answered quickly: Given a rectangle...

y (2007)

Pankaj K. Agarwal, Eyal Flato, Dan Halperin

Several algorithms for computing the Minkowski sum of two polygons in the plane begin by decomposing each polygon into convex subpolygons. We examine different methods for decomposing polygons by...

A Simple and Efficient Algorithm for High-Quality Line Labeling (2007)

A (1 + ")-Approximation Algorithm for 2-Line-Center (2007)

The interest in algorithms that automatically place labels on maps, graphs, or diagrams has increased with the advance in type-setting technology and the amount of information to be visualized....

Pankaj K. Agarwal, Cecilia M. Procopiuc, Kasturi R. Varadarajan

We consider the following instance of projective clustering, known as the 2-linecenter problem: Given a set S of n points in R 2, cover S by two strips so that the maximum width of a strip is...

A Framework for Index Bulk Loading and (2007)

Pankaj K. Agarwal, Lars Arge, Octavian Procopiuc, Jeffrey Scott Vitter

Abstract. In this paper we investigate automated methods for externalizing internal memory data structures. We consider a class of balanced trees that we call weight-balanced partitioning trees (or...

5 1 (2007)

Pankaj K. Agarwal, Mark De Berg, Sariel Har-peled, Mark H. Overmars, Micha Sharir

Abstract. Let P = fP1; : : : ; Pmg be a set of m convex polytopes in R

(d) (2007)

We derive improved bounds on the number of triangles or tetrahedra spanned by a set of n points in R d that are congruent to a given triangle or tetrahedron. More generally, let

. Let! (2007)

Pankaj K. Agarwal, Mark De Berg, Joachim Gudmundsson, Mikael Hammar, Herman J. Haverkort

x Let S be a set of n points in R 3

z (2007)

A box-tree is a bounding-box hierarchy that uses axis-aligned boxes as bounding volumes. The stabbing number of a box-tree with respect to a given type of query is the maximum number of nodes visited...

Occlusion Culling for Fast Walkthrough in Urban Areas (2007)

Pankaj K. Agarwal, Sariel Har-peled, Yusu Wang

This paper describes a fast algorithm, based on occlusion culling, for rendering complex urban environments. Occlusion culling has been widely used to achieve interactive frame rates for rendering...

y (2007)

Pankaj K. Agarwal, Eyal Flato, Dan Halperin

Several algorithms for computing the Minkowski sum of two polygons in the plane begin by decomposing each polygon into convex subpolygons. We examine dierent methods for decomposing polygons by their...

Reporting Intersecting Pairs of Polytopes in Two and Three Dimensions ⋆ (2007)

Pankaj K. Agarwal, Mark De Berg, Sariel Har-peled, Mark H. Overmars, Micha Sharir, Jan Vahrenhold

Abstract. Let P = {P1,..., Pm} be a set of m convex polytopes in R d, for d = 2, 3, with a total of n vertices. We present output-sensitive algorithms for reporting all k pairs of indices (i, j) such...

A Framework for Index Bulk Loading (2007)

Pankaj K. Agarwal, Lars Arge, Octavian Procopiuc, Jeffrey Scott Vitter

Abstract. In this paper we investigate automated methods for externalizing internal memory data structures. We consider a class of balanced trees that we call weight-balanced partitioning trees (or...

y (2007)

Pankaj K. Agarwal, Lars Arge, Jeff Erickson

We propose three indexing schemes for storing a set S of N points in the plane, each moving along a linear trajectory, so that a query of the following form can be answered quickly: Given a rectangle...

Reporting Intersecting Pairs of Polytopes in Two and Three Dimensions (2007)

Pankaj K. Agarwal, Mark De Berg, Sariel Har-peled, Mark H. Overmars, Micha Sharir, Jan Vahrenhold

Let P = fP 1 ; : : : ; Pm g be a set of m convex polytopes in R d , for d = 2; 3, with a total of n vertices. We present output-sensitive algorithms for reporting all k pairs of indices (i; j) such...

Approximation Algorithms for Minimum-Width Annuli and Shells (2007)

Pankaj K. Agarwal, Boris Aronov, Sariel Har-peled, Micha Sharir

The \roundness" of S can be measured by computing the width ! (S) of the thinnest spherical shell (or annulus in ) that contains S. This paper contains two main results related to computing :...

Occlusion Culling for Fast Walkthrough in Urban Areas (2007)

Yusu Wang Pankaj, Pankaj K. Agarwal, Sariel Har-peled

This paper describes a fast algorithm, based on occlusion culling, for rendering complex urban environments. Occlusion culling has been widely used to achieve interactive frame rates for rendering...

Approximating extent measures of points (2007)

Pankaj K. Agarwal, Sariel Har-peled, Kasturi R. Varadarajan

We present a general technique for approximating various descriptors of the extent of a set P of n points in R d. For a given extent measure and a parameter "> 0, it computes in time O(n...

Staying in the Middle: Exact and Approximate Medians in R (2007)

And For Moving, Pankaj K. Agarwal, Mark De Berg, Jie Gao, Leonidas J. Guibas, ...

Many divide-and-conquer based geometric algorithms and order-statistics problems ask for a point that lies \in the middle" of a given point set. We study several fundamental problems of this...

Reporting Intersecting Pairs of Polytopes in Two and Three Dimensions (2007)

Pankaj K. Agarwal, Mark De Berg, Sariel Har-peled, Mark H. Overmars, Micha Sharir, Jan Vahrenhold

d , for d = 2; 3, with a total of n vertices. We present output-sensitive algorithms for reporting all k pairs of indices (i; j) such that P i intersects P j . For the planar case we describe a...

Untangling Triangulations through Local Explorations ∗ (2007)

Pankaj K. Agarwal, Bardia Sadri, Hai Yu

In many applications it is often desirable to maintain a valid mesh within a certain domain that deforms over time. During a period for which the underlying mesh topology remains unchanged, the...

Embeddings of surfaces, curves, and moving points in euclidean space (2007)

� �� denote the position of � � at time � , and set �� . We assume (2007)

In this paper we show that dimensionality reduction (i.e., Johnson-Lindenstrauss lemma) preserves not only the distances between static points, but also between moving points, and more generally...

State of the Union (of Geometric Objects): A Review ∗ (2007)

Approved: (2007)

Junyi Xie, Pankaj K. Agarwal, Shivnath Babu, Jeff Chase, Philip S. Yu, Junyi Xie, ...

Recent years have witnessed a rapid rise of a new class of data-intensive applications in which data arrive as transient, high-volume streams. Financial data processing, network monitoring, and...

Pankaj K. Agarwal, János Pach, Micha Sharir

Let C be a set of geometric objects in R d. The combinatorial complexity of the union U(C) of C is the total number of faces of all dimensions, of the arrangement of the boundaries of the objects,...

Computing the volume of the union of cubes (2007)

Kinetic and Dynamic Data Structures for Closest Pairs and All Nearest Neighbors ∗ (2007)

Let C be a set of n axis-aligned cubes in R 3, and let U(C) denote the union of C. We present an algorithm that can compute the volume of U(C) in time O(n 4/3 log n). The previously best known...

Pankaj K. Agarwal, Roel Apfelbaum, George Purdy, Micha Sharir

We present simple fully dynamic and kinetic data structures, which are variants of a dynamic 2-dimensional range tree, for maintaining the closest pair and all nearest neighbors for a set of n moving...

We consider the problem of bounding the maximum possible number fk,d(n) of ksimplices that are spanned by a set of n points in R d and are similar to a given simplex. We first show that f2,3(n) = O(n...

Kinetic and Dynamic Data Structures for Closest Pairs and All Nearest Neighbors ∗ (2007)

Embeddings of surfaces, curves, and moving points in euclidean space (2007)

We present simple fully dynamic and kinetic data structures, which are variants of a dynamic 2-dimensional range tree, for maintaining the closest pair and all nearest neighbors for a set of n moving...

Embeddings of surfaces, curves, and moving points in euclidean space (2007)

In this paper we show that dimensionality reduction (i.e., Johnson-Lindenstrauss lemma) preserves not only the distances between static points, but also between moving points, and more generally...

A scalable algorithm for dispersing population (2007)

In this paper we show that dimensionality reduction (i.e., Johnson-Lindenstrauss lemma) preserves not only the distances between static points, but also between moving points, and more generally...

Approved: (2007)

Junyi Xie, Pankaj K. Agarwal, Shivnath Babu, Jeff Chase, Philip S. Yu, Junyi Xie, ...

Recent years have witnessed a rapid rise of a new class of data-intensive applications in which data arrive as transient, high-volume streams. Financial data processing, network monitoring, and...

Govindarajan, Sathish, Dietze, Michael C., Agarwal, Pankaj K., Clark, James S.

Models of forest ecosystems are needed to understand how climate and land-use change can impact biodiversity. In this paper we describe an ecological dispersal model developed for the specific case...

Scalable continuous queries processing by tracking hotspots (2006)

From point cloud to grid DEM: A scalable approach (2006)

Abstract This paper considers the problem of scalably processing a large number of continuous queries.We propose a flexible framework with novel data structures and algorithms for group-processing...

Pankaj K. Agarwal, Lars Arge, Andrew Danner

Summary. Given a set S of points in R 3 sampled from an elevation function H: R 2 → R, we present a scalable algorithm for constructing a grid digital elevation model (DEM). Our algorithm consists...

by (2006)

Andrew Danner, Lars Arge Supervisor, Pankaj K. Agarwal, Herbert Edelsbrunner, Helena Mitasova, Andrew Danner, ...

Modern remote sensing methods such a laser altimetry (lidar) and Interferometric Synthetic Aperture Radar (IfSAR) produce georeferenced elevation data at unprecedented rates. Many Geographic...

Robust shape fitting via peeling and grating coresets (2006)

Scalable continuous queries processing by tracking hotspots (2006)

Let P be a set of n points in R d. A subset S of P is called a (k, ε)-kernel if for every direction, the direction width of S ε-approximates that of P, when k “outliers ” can be ignored in that...

by (2006)

Andrew Danner, Lars Arge Supervisor, Pankaj K. Agarwal, Herbert Edelsbrunner, Helena Mitasova, Andrew Danner, ...

Modern remote sensing methods such a laser altimetry (lidar) and Interferometric Synthetic Aperture Radar (IfSAR) produce georeferenced elevation data at unprece-dented rates. Many Geographic...

Robust shape fitting via peeling and grating coresets (2006)

This paper considers the problem of scalably processing a large number of continuous queries. We propose a flexible framework with novel data structures and algorithms for group-processing and...

Scalable continuous queries processing by tracking hotspots (2006)

Abstract Let P be a set of n points in Rd. A subset S of P is called a (k, ")-kernel if for every direction, thedirection width of S "-approximates that of P, when k...

Model-driven dynamic control of embedded wireless sensor networks (2006)

This paper considers the problem of scalably processing a large number of continuous queries. We propose a flexible framework with novel data structures and algorithms for group-processing and...

Paul G. Flikkema, Pankaj K. Agarwal, James S. Clark, Carla Ellis, Alan Gelf, Kamesh Munagala

Abstract. Next-generation wireless sensor networks may revolutionize understanding of environmental change by assimilating heterogeneous data, assessing the relative value and costs of data...

Robust shape fitting via peeling and grating coresets (2006)

Computing a center-transversal line (2006)

Let P be a set of n points in R d. A subset S of P is called a (k, ε)-kernel if for every direction, the direction width of S ε-approximates that of P, when k “outliers ” can be ignored in that...

Pankaj K. Agarwal, Sergio Cabello, J. Antoni, Sellarès Micha Sharir

A center-transversal line for two finite point sets in R 3 is a line with the property that any closed halfspace that contains it also contains at least one third of each point set. It is known that...

Robust shape fitting via peeling and grating coresets (2006)

Computing a center-transversal line (2006)

Let P be a set of n points in R d. A subset S of P is called a (k, ε)-kernel if for every direction, the direction width of S ε-approximates that of P, when k “outliers ” can be ignored in that...

Pankaj K. Agarwal, Sergio Cabello, J. Antoni, Sellarès Micha Sharir

A center-transversal line for two finite point sets in R 3 is a line with the property that any closed halfspace that contains it also contains at least one third of each point set. It is known that...

Robust shape fitting via peeling and grating coresets (2006)

From point cloud to grid DEM: A scalable approach (2006)

Let T be a set of n points in R d. We show that a (k, ε)-kernel of T of size O(k/ε (d−1)/2) can be computed in time O(n + k 2 /ε d−1), where a (k, ε)-kernel is a subset of T that...

Pankaj K. Agarwal, Lars Arge, Andrew Danner

Summary. Given a set S of points in R 3 sampled from an elevation function H: R 2 → R, we present a scalable algorithm for constructing a grid digital elevation model (DEM). Our algorithm consists...

Scalable continuous queries processing by tracking hotspots (2006)

Segmenting motifs in protein-protein interface surfaces (2006)

This paper considers the problem of scalably processing a large number of continuous queries. We propose a flexible framework with novel data structures and algorithms for group-processing and...

Jeff M. Phillips, Johannes Rudolph, Pankaj K. Agarwal

Abstract. Protein-protein interactions form the basis for many intercellular events. In this paper we develop a tool for understanding the structure of these interactions. Specifically, we define a...

Monitoring continuous band-join queries over dynamic data (2005)

Geometric approximation via coresets (2005)

Abstract. A continuous query is a standing query over a dynamic data set whose query result needs to be constantly updated as new data arrive. We consider the problem of constructing a data structure...

Pankaj K. Agarwal, Sariel Har-peled, R. Varadarajan

Abstract. The paradigm of coresets has recently emerged as a powerful tool for efficiently approximating various extent measures of a point set P. Using this paradigm, one quickly computes a small...

Geometric approximation via coresets (2005)

Pankaj K. Agarwal, Sariel Har-peled, Kasturi R. Varadarajan

The paradigm of coresets has recently emerged as a powerful tool for efficiently approximating various extent measures of a point set P. Using this paradigm, one quickly computes a small subset Q of...

BioGeometry Software Coresets for Shape Fitting and Kinetic Data Structures (2005)

Pankaj K. Agarwal, Hai Yu

descriptors of the extent of a set P of n points in R d has found many useful applications in shape analysis, data mining and other areas. These descriptors, called extent measures, either compute...

An optimal dynamic interval stabbing-max data structure (2005)

Pankaj K. Agarwal, Lars Arge, Ke Yi

1 Introduction In this paper we consider data structures for thestabbing-max problem (also sometimes called the rectangle intersection with priorities problem). That is, theproblem of dynamically...

Monitoring continuous band-join queries over dynamic data (2005)

Monitoring continuous band-join queries over dynamic data (2005)

We present the first nontrivial data structure for this problem that simultaneously achieves subquadratic space and sublinear query time. This is achieved by first decomposing the original problem...

An optimal dynamic interval stabbing-max data structure (2005)

We present the first nontrivial data structure for this problem that simultaneously achieves subquadratic space and sublinear query time. This is achieved by first decomposing the original problem...

Pankaj K. Agarwal, Lars Arge, Ke Yi

In this paper we consider the dynamic stabbing-max problem, that is, the problem of dynamically maintaining a set S of n axis-parallel hyper-rectangles in d, where each rectangle s ∈ S has a...

Lower bound for sparse euclidean spanners (2005)

Object Space Segmentation by Geometric Reference Structures (2005)

Given a one-dimensional graph ¢ such that any two consecutive nodes are unit distance away, and such that the minimum number of links between any two nodes (the diameter of ¢ ) is...

Pankaj K. Agarwal, David Brady

Efficient algorithms for bichromatic separability (2005)

Pankaj K. Agarwal, Boris Aronov, Vladlen Koltun

Geometric approximation via coresets (2005)

Pankaj K. Agarwal, Sariel Har-peled, Kasturi R. Varadarajan

The paradigm of coresets has recently emerged as a powerful tool for efficiently approximating various extent measures of a point set P. Using this paradigm, one quickly computes a small subset Q of...

Guarding a terrain by two watchtowers (2005)

Pankaj K. Agarwal, Sergey Bereg, Ovidiu Daescu, Simeon Ntafos, Micha Sharir, Binhai Zhu

Given a polyhedral terrain T with n vertices, the two-watchtower problem for T asks to find two vertical segments, called watchtowers, of smallest common height, whose bottom endpoints (bases) lie on...

Monitoring continuous band-join queries over dynamic data (2005)

An optimal dynamic interval stabbing-max data structure (2005)

Abstract. A continuous query is a standing query over a dynamic data set whose query result needs to be constantly updated as new data arrive. We consider the problem of constructing a data structure...

Pankaj K. Agarwal, Lars Arge, Ke Yi

In this paper we consider the dynamic stabbing-max problem, that is, the problem of dynamically maintaining a set S of n axis-parallel hyper-rectangles in d, where each rectangle s ∈ S has a weight...

Guarding a terrain by two watchtowers (2005)

Pankaj K. Agarwal, Sergey Bereg, Ovidiu Daescu, Haim Kaplan, Simeon Ntafos, Micha Sharir, ...

Given a polyhedral terrain T with n vertices, the two-watchtower problem for T asks to find two vertical segments, called watchtowers, of smallest common height, whose bottom endpoints (bases) lie on...

Lenses in arrangements of pseudo-circles and their applications (2004)

Pankaj K. Agarwal, Micha Sharir, Eran Nevo, Shakhar Smorodinsky

Abstract. A collection of simple closed Jordan curves in the plane is called a family of pseudo-circles if any two of its members intersect at most twice. A closed curve composed of two subarcs of...

Abstract An Nguyen £ (2004)

Pankaj K. Agarwal, Leonidas Guibas, Li Zhang, Daniel Russel

In this paper, we propose to study deformable necklaces — flexible chains of balls, called beads, in which only adjacent balls may intersect. Such objects can be used to model macromolecules,...

Practical Methods for Shape Fitting and Kinetic Data Structures using Core Sets (2004)

Hai Yu, Pankaj K. Agarwal, Raghunath Poreddy, Kasturi R. Varadarajan

The notion of ε-kernel was introduced by Agarwal et al. [5] to set up a unified framework for computing various extent measures of a point set P approximately. Roughly speaking, a subset Q ⊆ P is...

Practical Methods for Shape Fitting and Kinetic Data Structures using Core Sets (2004)

Hai Yu, Pankaj K. Agarwal, Raghunath Poreddy, Kasturi R. Varadarajan

Abstract The notion of "-kernel was introduced by Agarwal et al. [5] to set up a unified framework forcomputing various extent measures of a point set P approximately. Roughly speaking, a...

Independent set of intersection graphs of convex objects in 2D (2004)

Lenses in arrangements of pseudo-circles and their applications (2004)

Abstract. The intersection graph of a set of geometric objects is defined as agraph G = (S; E) in which there is an edge between two nodes si; sj 2 S if si " sj 6 =;. The problem of...

Pankaj K. Agarwal, Eran Nevo, Janos Pach, Rom Pinchasi, Micha Sharir, Shakhar Smorodinsky

A collection of simple closed Jordan curves in the plane is called a family of pseudo-circles if any two of its members intersect at most twice. A closed curve composed of two subarcs of distinct...

Independent set of intersection graphs of convex objects in 2D (2004)

Independent set of intersection graphs of convex objects in 2D (2004)

Abstract. The intersection graph of a set of geometric objects is defined as a £¥¤§¦©¨�� graph in which there is an edge between two �� ¨...

Practical Methods for Shape Fitting and Kinetic Data Structures using Core Sets (2004)

The intersection graph of a set of geometric objects is defined as a £¥¤§¦©¨�� graph in which there is an edge between two �� ¨ nodes...

Hai Yu, Pankaj K. Agarwal, Raghunath Poreddy, Kasturi R. Varadarajan

Abstract The notion of "-kernel was introduced by Agarwal et al. [5] to set up a unified framework for computing various extent measures of a point set P approximately. Roughly speaking, a...

Efficient tradeoff schemes in data structures for querying moving objects (2004)

Pankaj K. Agarwal, Lars Arge, Jeff Erickson, Hai Yu

The ability to represent and query continuously moving objects is important in many applications of spatio-temporal database systems. In this paper we develop data structures for answering various...

Practical Methods for Shape Fitting and Kinetic Data Structures using Core Sets (2004)

Hai Yu, Pankaj K. Agarwal, Raghunath Poreddy, Kasturi R. Varadarajan

The notion of ε-kernel was introduced by Agarwal et al. [5] to set up a unified framework for computing various extent measures of a point set P approximately. Roughly speaking, a subset Q ⊆ P is...

On lines avoiding unit balls in three dimensions (2004)

Pankaj K. Agarwal, Boris Aronov, Vladlen Koltun, Micha Sharir

Let B be a set of n unit balls in R 3. We show that the combinatorial complexity of the space of lines in R 3 that avoid all the balls of B is O(n 3+ε), for any ε> 0. This result has connections...

Algorithms for center and Tverberg points (2004)

Pankaj K. Agarwal, Micha Sharir, Emo Welzl

ABSTRACT SIMPLIFICATION, ESTIMATION AND CLASSIFICATION OF GEOMETRIC OBJECTS (2004)

Nabil H. Mustafa, Pankaj K. Agarwal, Herbert Edelsbrunner, Shankar Krishnan, Carlo Tomasi, Nabil H. Mustafa, ...

The main focus of this thesis is on the analysis, via simplification, estimation and clas-sification, of discrete geometric objects using methods from discrete and combinatorial geometry. Geometric...

Cache-oblivious data structures for orthogonal range searching (2003)

Pankaj K. Agarwal, Lars Arge, Andrew Danner, Bryan Holl

ABSTRACT We develop cache-oblivious data structures for orthogonal range searching, the problem of finding all T points in a set of N points in Rd lying in a query hyper-rectangle. Cacheoblivious...

Hausdorff distance under translation for points, disks, and balls (2003)

Pankaj K. Agarwal, Sariel Har-peled, Micha Sharir, Yusu Wang

We study the shape matching problem under the Hausdorff distance and its variants. In the first part of the paper, we consider two sets A, B of balls in R d, d = 2, 3, and wish to find a translation...

CRB-tree: An efficient indexing scheme for range-aggregate queries (2003)

Sathish Govindarajan, Pankaj K. Agarwal, Lars Arge

Abstract. We propose a new indexing scheme, called the CRB-tree, for efficiently answering range-aggregate queries. The range-aggregate problem is defined as follows: Given a set of weighted points...

I/O-efficient structures for orthogonal range max and stabbing max queries (2003)

Streaming geometric optimization using graphics hardware (2003)

Abstract Due to their important applications in e.g. temporal and spatial database systems, range searching and its variants have been studied extensively in both the computational geometry and...

Pankaj K. Agarwal, Shankar Krishnan, Nabil H. Mustafa

2 1

Staying in the middle: Exact and approximate medians in R 1 and R 2 for moving points, manuscript (2003)

Pankaj K. Agarwal, Mark Berg, Jie Gao, Leonidas J. Guibas, Sariel Har-peled

Many divide-and-conquer based geometric algorithms and order-statistics problems ask for a point that lies “in the middle ” of a given point set. We study several fundamental problems of this...

Octavian Procopiuc, Pankaj K. Agarwal, Lars Arge, Jeffrey Scott Vittery

Streaming geometric optimization using graphics hardware (2003)

Pankaj K. Agarwal, Shankar Krishnan, Nabil H. Mustafa

Abstract. In this paper we propose algorithms for solving a variety of geometric optimization problems on a stream of points in � 2 or � 3. These problems include various extent measures (e.g....

CRB-tree: An efficient indexing scheme for range-aggregate queries (2003)

Sathish Govindarajan, Pankaj K. Agarwal, Lars Arge

Abstract. We propose a new indexing scheme, called the CRB-tree, for efficiently answering range-aggregate queries. The range-aggregate problem is defined as follows: Given a set of weighted points...

Cache-oblivious data structures for orthogonal range searching (2003)

Pankaj K. Agarwal, Lars Arge, Andrew Danner, Bryan Holl

We develop cache-oblivious data structures for orthogonal range searching, the problem of finding all T points in a set of N points in R d lying in a query hyper-rectangle. Cacheoblivious data...

Approved: (2003)

David Paul Kowalski, A. Board, Pankaj K. Agarwal

This thesis describes a fault-tolerant system for pose estimation for the human body in real time using a distributed array of computers with attached cameras. The system allows for random placement...

Octavian Procopiuc, Pankaj K. Agarwal, Lars Arge, Jeffrey Scott Vitter

Abstract. In this paper we propose a new data structure, called the Bkd-tree, for indexing large multi-dimensional point data sets. The Bkd-tree is an I/O-efficient dynamic data structure based on...

CRB-tree: An efficient indexing scheme for range-aggregate queries (2003)

Sathish Govindarajan, Pankaj K. Agarwal, Lars Arge

Abstract. We propose a new indexing scheme, called the CRB-tree, for efficiently answering range-aggregate queries. The range-aggregate problem is defined as follows: Given a set of weighted points...

Octavian Procopiuc, Pankaj K. Agarwal, Lars Arge, Jeffrey Scott Vitter

Abstract. In this paper we propose a new index structure, called the Bkd-tree, for indexing large multi-dimensional point data sets. The Bkdtree is an I/O-efficient dynamic data structure based on...

I/O-efficient structures for orthogonal range max and stabbing max queries (2003)

Streaming geometric optimization using graphics hardware (2003)

Due to their important applications in e.g. temporal and spatial database systems, range searching and its variants have been studied extensively in both the computational geometry and database...

Pankaj K. Agarwal, Shankar Krishnan, Nabil H. Mustafa

2 1

Octavian Procopiuc, Pankaj K. Agarwal, Lars Arge, Jeffrey Scott Vitter

Abstract. In this paper we propose a new data structure, called the Bkd-tree, for indexing large multi-dimensional point data sets. The Bkd-tree is an I/O-efficient dynamic data structure based on...

Computing Maximally Separated Sets in the Plane and Independent Sets in the Intersection Graph of Unit Disks (2003)

Pankaj K. Agarwal, Mark Overmars, Micha Sharir

Given an integer 1 n, we wish to find a maximally separated subset I S of size k; this is a subset for which the minimum among the pairwise distances between its points is as large as possible. The...

Staying in the middle: Exact and approximate medians in R 1 and R 2 for moving points, manuscript (2003)

Pankaj K. Agarwal, Mark Berg, Jie Gao, Leonidas J. Guibas, Sariel Har-peled

Many divide-and-conquer based geometric algorithms and order-statistics problems ask for a point that lies “in the middle ” of a given point set. We study several fundamental problems of this...

Hausdorff distance under translation for points, disks, and balls (2003)

Hausdorff distance under translation for points, disks, and balls (2003)

Pankaj K. Agarwal, Sariel Har-peled, Micha Sharir, Yusu Wang

We study the shape matching problem under the Hausdorff distance and its variants. In the first part of the paper, we consider two sets A, B of balls in R d, d = 2, 3, and wish to find a translation...

CRB-Tree: An Efficient Indexing Scheme for (2003)

Range Aggregate Queries, Sathish Govindarajan, Pankaj K. Agarwal, Lars Arge

We propose a new indexing scheme, called the CRB-tree, for efficiently answering range-aggregate queries. The range-aggregate problem is defined as follows: Given a set of weighted points in R ,...

Abstract An Nguyen £ (2003)

Pankaj K. Agarwal, Leonidas Guibas, Li Zhang, Daniel Russel

In this paper, we propose to study deformable necklaces — flexible chains of balls, called beads, in which only adjacent balls may intersect. Such objects can be used to model macromolecules,...

Staying in the middle: Exact and approximate medians in R 1 and R 2 for moving points, manuscript (2003)

Pankaj K. Agarwal, Mark Berg, Jie Gao, Leonidas J. Guibas, Sariel Har-peled

We study the problem of “staying in the middle”: we have a set of points moving in a geometric space and wish to maintain another point (possibly one of the given points, but not necessarily)...

A Simple and Efficient Algorithm for High-Quality Line Labeling (2002)

Wolff, Alexander, Knipping, Lars, Kreveld, Marc Van, Strijk, Tycho, Agarwal, Pankaj K.

Lenses in arrangements of pseudo-circles and their applications (2002)

Pach, János, Agarwal, Pankaj K., Nevo, E., Pinchasi, Rom, Sharir, Micha, Smorodinsky, Shakhar

Near-linear time approximation algorithms for curve simplification (2002)

Fast molecular shape matching using contact maps (2002)

Abstract We consider the problem of approximating a polygonal curve P under a given error criterionby another polygonal curve P 0 whose vertices are a subset of the vertices of P. The goal is...

Pankaj K. Agarwal, Nabil H. Mustafa, Yusu Wang

In this paper, we study the problem of computing the similarity of two protein structures by measuring their contact-map overlap. Contact-map overlap abstracts the problem of computing the similarity...

Fast molecular shape matching using contact maps (2002)

Pankaj K. Agarwal, Nabil H. Mustafa, Yusu Wang

In this paper, we study the problem of computing the similarity of two protein structures by measuring their contact-map overlap. Contact-map overlap abstracts the problem of computing the similarity...

Translating a planar object to maximize point containment (2002)

Pankaj K. Agarwal, Torben Hagerup, Rahul Ray, Micha Sharir, Michiel Smid, Emo Welzl

Abstract. Let C be a compact set in R

Range Searching in Categorical Data: Colored Range Searching on Grid (2002)

Pankaj K. Agarwal, Sathish Govindarajan, S. Muthukrishnan

Range searching, a fundamental problem in numerous applications areas, has been widely studied in computational geometry and spatial databases. Given a set of geometric objects, a typical range query...

Kinetic Medians and kd-Trees (2002)

Pankaj K. Agarwal, Jie Gao, Leonidas J. Guibas

We propose algorithms for maintaining two variants of kd- trees of a set of moving points in the plane. A pseudo kd-tree allows the number of points stored in the two children to di#er by a constant...

Computing the Detour of Polygonal Curves (2002)

Pankaj K. Agarwal, Pankaj K. Agarwal, Rolf Klein, Rolf Klein, Christian Knauer, Christian Knauer, ...

Let P be a simple polygonal chain in E with n edges. The detour of P between two points, x and y, is the ratio between the length of P between x any y and their Euclidean distance.

Near-Linear Time Approximation Algorithms for Curve Simplification (2002)

Pankaj K. Agarwal, Sariel Har-peled, Nabil H. Mustafa, Yusu Wang

We consider the problem of approximating a polygonal curve P under a given error criterion by another polygonal curve P whose vertices are a subset of the vertices of P . The goal is to minimize the...

Computing Approximate Shortest Paths on Convex Polytopes (2002)

Pankaj K. Agarwal, Sariel Har-peled, Meetesh Karia

The algorithms for computing a shortest path on a polyhedral surface are slow, complicated, and numerically unstable. We have developed and implemented a robust and efficient algorithm for computing...

Motion Planning for a Convex Polygon in a Polygonal Environment (2002)

Translating a planar object to maximize point containment (2002)

We study the motion-planning problem for a convex m-gon P in a planar polygonal environment Q bounded by n edges. We give the rst algorithm that constructs the entire free con guration space (the...

Pankaj K. Agarwal, Torben Hagerup, Rahul Ray, Micha Sharir, Michiel Smid, Emo Welzl

Abstract. Let � be a compact set in Ê and let Ë beasetofÒpoints in Ê.We consider the problem of computing a translate of � that contains the maximum number, � £ , of points of Ë. It is...

A monte carlo algorithm for fast projective clustering (2002)

Cecilia M. Procopiuc, Michael Jonesý, Pankaj K. Agarwal, T. M. Muraliý

We propose a mathematical formulation for the notion of optimal projective cluster, starting from natural requirements on the density of points in subspaces. This allows us to develop a Monte Carlo...

A monte carlo algorithm for fast projective clustering (2002)

Cecilia M. Procopiuc, Michael Jonesý, Pankaj K. Agarwal, T. M. Muraliý

We propose a mathematical formulation for the notion of optimal projective cluster, starting from natural requirements on the density of points in subspaces. This allows us to develop a Monte Carlo...

Near-linear time approximation algorithms for curve simplification (2002)

Pankaj K. Agarwal, Sariel Har-peled, Nabil H. Mustafa, Yusu Wang

We consider the problem of approximating a polygonal curve P under a given error criterion by another polygonal curve P ′ whose vertices are a subset of the vertices of P. The goal is to minimize...

Hausdorff Distance under Translation for Points, Disks, (2002)

Pankaj K. Agarwal, Sariel Har-peled, Micha Sharir, Yusu Wang

Let A and B be two sets of balls in R d, d = 2, 3. We measure similarity between A and B by computing the minimum Hausdorff distance between A + t and B, where the minimum is taken either over all...

Kinetic medians and kd-trees (2002)

Pankaj K. Agarwal, Jie Gao, Leonidas J. Guibas

Abstract. We propose algorithms for maintaining two variants of kd-trees of a set of moving points in the plane. A pseudo kd-tree allows the number of points stored in the two children to differ. An...

On the Number of Congruent Simplices in a Point Set (2002)

Hausdorff Distance under Translation for Points, Disks, and Balls (2002)

For 1 k d 1, let f k (n) be the maximum possible number of k-simplices spanned by a set of n points in R that are congruent to a given k-simplex. We prove that f ), for any " > 0, f ), and f...

Pankaj K. Agarwal, Sariel Har-peled, Micha Sharir, Yusu Wang

Let A and B be two sets of balls in R^d, d = 2, 3. We measure similarity between A and B by computing the minimum Hausdorff distance between A+t and B, where the minimum is taken either over all...

Deformable free-space tilings for kinetic collision detection (2002)

Pankaj K. Agarwal, Julien Basch, Leonidas J. Guibas, John Hershberger, Li Zhang

We present kinetic data structures for detecting collisions between a set of polygons that are moving continuously. Unlike classical collision detection methods that rely on bounding volume...

Time responsive external data structures for moving points (2001)

Pankaj K. Agarwal, Lars Arge

Abstract. We develop external data structures for storing points in one or two dimensions, each moving along a linear trajectory, so that a range query at a given time tq can be answered efficiently....

Time responsive external data structures for moving points (2001)

Pseudoline arrangements: Duality. algorithms and applications (2001)

Abstract. We develop external data structures for storing points in one or two dimensions, each moving along a linear trajectory, so that a range query at a given time tq can be answered efficiently....

Maintaining the approximate extent measures of moving points (2001)

A collection L of x-monotone unbounded Jordan curves in the plane is called a family of pseudolines if every pair of curves intersects in at most one point, and the two curves cross each other there....

Pankaj K. Agarwal, Sariel Har-peled

We present approximation algorithms for maintaining various descriptors of the extent of moving points in R

A time responsive indexing scheme for moving points (2001)

Pankaj K. Agarwal, Lars Arge

z We develop new indexing schemes for storing a set of points in one or two dimensions, each moving along a linear trajectory, so that a range query at a given future time t q can be answered...

Randomized algorithms for geometric optimization problems (2001)

Pankaj K. Agarwal, Sandeep Sen

This chapter reviews randomization algorithms developed in the last few years to solve a wide range of geometric optimization problems. We rst review a number of general techniques, including...

Maintaining Approximate Extent Measures of Moving Points (2001)

Pankaj K. Agarwal, Sariel Har-peled

We present approximation algorithms for maintaining various descriptors of the extent of moving points in R . We rst describe a data structure for maintaining the smallest orthogonal rectangle...

Exact and Approximation Algorithms for Minimum-Width Cylindrical Shells (2001)

Pseudo-line Arrangements: Duality, Algorithms, and Applications (2001)

Let S be a set of n points in R 3 . Let ! = ! (S) be the width (i.e., thickness) of a minimum-width infinite cylindrical shell (the region between two co-axial cylinders) containing S. We first...

Pseudoline arrangements: Duality. algorithms and applications, manuscript (2001)

A collection L of n x-monotone unbounded Jordan curves in the plane is called a family of pseudo-lines if every pair of curves intersect in at most one point, and the two curves cross each other...

On Levels in Arrangements of Lines, Segments, Planes, and Triangles (2001)

Abstract A collection L of n x-monotone unbounded Jordan curves in the plane is called a family of pseudo-lines if every pair of curves intersect in at most one point, and the two curves cross each...

Pankaj K. Agarwal, Boris Aronov, Timothy M. Chan, Micha Sharir

We consider the problem of bounding the complexity of the k-th level in an arrangement of n curves or surfaces, a problem dual to, and an extension of, the well-known k-set problem. Among other...

Curvature-Constrained Shortest Paths in a Convex Polygon (2000)

Agarwal, Pankaj K., Biedl, Thérèse, Lazard, Sylvain, Robbins, Steve, Suri, Subhash, Whitesides, Sue

Let $B$ be a point robot moving in the plane, whose path is constrained to have curvature at most $1$, and let $\poly$ be a convex polygon with $n$ vertices. We study the collision-free, optimal path...

Curvature-Constrained Shortest Paths in a Convex Polygon (2000)

Agarwal, Pankaj K., Biedl, Thérèse, Lazard, Sylvain, Robbins, Steve, Suri, Subhash, Whitesides, Sue

Let $B$ be a point robot moving in the plane, whose path is constrained to have curvature at most $1$, and let $\poly$ be a convex polygon with $n$ vertices. We study the collision-free, optimal path...

Curvature-Constrained Shortest Paths in a Convex Polygon (2000)

Agarwal, Pankaj K., Biedl, Thérèse, Lazard, Sylvain, Robbins, Steve, Suri, Subhash, Whitesides, Sue

Let $B$ be a point robot moving in the plane, whose path is constrained to have curvature at most $1$, and let $\poly$ be a convex polygon with $n$ vertices. We study the collision-free, optimal path...

Deformable free space tilings for kinetic collision detection (2000)

Pankaj K. Agarwal, Julien Basch, Leonidas J. Guibas, John Hershberger, Li Zhang

We present kinetic data structures for detecting collisions between a set of polygons that are not only moving continuously but whose shapes can also change continuously with time. We construct a...

Indexing moving points (2000)

Pankaj K. Agarwal, Lars Arge, Jeff Erickson B

We propose three indexing schemes for storing a set S of N points in the plane, each moving along a linear trajectory, so that any query of the following form can be answered quickly: Given a...

Deformable free space tilings for kinetic collision detection (2000)

Pankaj K. Agarwal, Julien Basch, Leonidas J. Guibas, John Hershberger, Li Zhang

We present kinetic data structures for detecting collisions between a set of polygons that are not only moving continuously but whose shapes can also vary continuously with time. Unlike classical...

Penetration depth of two convex polytopes in 3D (2000)

Pankaj K. Agarwal, Leonidas J. Guibas, Sariel Har-peled, Alexander Rabinovitch, Micha Sharir

Let A and B be two convex polytopes in R 3 with m and n facets, respectively. The penetration depth of A and B, denoted as (A; B), is the minimum distance by which A has to be translated so that A...

Penetration depth of two convex polytopes in 3D (2000)

Pankaj K. Agarwal, Leonidas J. Guibas, Sariel Har-peled, Alexander Rabinovitch, Micha Sharir

Let A and B be two convex polytopes in R 3 with m and n facets, respectively. The penetration depth of A and B, denoted as (A; B), is the minimum distance by which A has to be translated so that A...

Computing the Penetration Depth of Two Convex Polytopes in 3D (2000)

Pankaj K. Agarwal, Leonidas J. Guibas, Sariel Har-peled, Alexander Rabinovitch, Micha Sharir

Let A and B be two convex polytopes in R 3 with m and n facets, respectively. The penetration depth of A and B, denoted as (A; B), is the minimum distance by which A has to be translated so that A...

Maintaining the Approximate Extent Measures of Moving Points (2000)

Pankaj K. Agarwal, Sariel Har-peled

We present approximation algorithms for maintaining various descriptors of the extent of moving points in R d . We first describe a data structure for maintaining the smallest orthogonal rectangle...

Occlusion Culling Using Exact Shadow Computations and Ray-Shooting Queries (2000)

Pavan K. Desikan, T. M. Murali, Pankaj K. Agarwal

Occlusion culling is a powerful and general technique used in computer graphics for rendering large scenes quickly. It determines the visible scene by computing a small superset of the set of visible...

Indexing Moving Points (2000)

Pankaj K. Agarwal, Lars Arge, Jeff Erickson

) Pankaj K. Agarwal Lars Arge y Jeff Erickson z Submitted to 19th ACM Symposium on Principles of Database Systems. November 8, 1999 Abstract We propose three indexing schemes for storing a set S of N...

Approximation Algorithms for Layered Manufacturing (2000)

Pankaj K. Agarwal, Pavan K. Desikan, Where A

An important problem in layered manufacturing is the choice of a good build direction, which influences the quality and the cost of manufacturing the object. We present efficient algorithms for...

Deformable Free Space Tilings for Kinetic Collision Detection (2000)

Pankaj K. Agarwal, Julien Basch, Leonidas J. Guibas, John Hershberger, Li Zhang

We present kinetic data structures for detecting collisions between a set of polygons that are not only moving continuously but whose shapes can also vary continuously with time. Unlike classical...

Randomized Algorithms for Geometric Optimization Problems (2000)

Pankaj K. Agarwal, Sandeep Sen

This chapter reviews randomization algorithms developed in the last few years to solve a wide range of geometric optimization problems. We review a number of general techniques, including randomized...

Approximation Algorithms for Projective Clustering (2000)

Pankaj K. Agarwal, Cecilia M. Procopiuc

We consider the following two instances of the projective clustering problem: Given a set S of n points in R d and an integer k ? 0; cover S by k hyper-strips (resp. hyper-cylinders) so that the...

Deformable free space tilings for kinetic collision detection (2000)

Pankaj K. Agarwal, Julien Basch, Leonidas J. Guibas, John Hershberger, Li Zhang

We present kinetic data structures for detecting collisions between a set of polygons that are not only moving continuously but whose shapes can also vary continuously with time. Unlike classical...

Y.: Near-linear time approximation algorithms for path simplification (2000)

Pankaj K. Agarwal, Sariel Har-peled, Nabil H. Mustafa, Yusu Wang

Abstract. We consider the problem of approximating a polygonal curve under a given error criterion by another polygonal curve whose vertices are a subset of the vertices of. The goal is to minimize...

Emerging Challenges in Computational Topology (1999)

Bern, Marshall, Eppstein, David, Agarwal, Pankaj K., Amenta, Nina, Chew, Paul, Dey, Tamal, ...

Here we present the results of the NSF-funded Workshop on Computational Topology, which met on June 11 and 12 in Miami Beach, Florida. This report identifies important problems involving both...

Emerging challenges in computational topology (1999)

Marshall Bern, Pankaj K. Agarwal, Nina Amenta, Paul Chew, Tamal Dey, David P. Dobkin, ...

Here we present the results of the NSF-funded Workshop on Computational Topology, which met on June 11 and 12 in Miami Beach, Florida. This report identifies

Lower bounds for kinetic planar subdivisions (1999)

Pankaj K. Agarwal, Julien Basch, Mark De Berg, Leonidas J. Guibas, John Hershberger

We revisit the notion of kinetic efficiency for non-canonically-defined discrete attributes of moving data, like binary space partitions and triangulations. Under reasonable computational models, we...

Lower bounds for kinetic planar subdivisions (1999)

Pankaj K. Agarwal, Julien Basch, Mark De Berg, Leonidas J. Guibas, John Hershberger

k We revisit the notion of kinetic efficiency for noncanonically-defined discrete attributes of moving data, like binary space partitions and triangulations. Under very general computational models,...

Computing Approximate Shortest Paths on Convex Polytopes (1999)

Pankaj K. Agarwal, Sariel Har-peled, Meetesh Karia

polyhedral Ç¥¸é¿¡ °¡Àå ÂªÀº °æ·Î¸¦ °è»êÇÏ±â¸¦ À§ÇØ »ê¹ýÀº ´À¸®°í, º¹ÀâÇÏ´Ù,±×¸®°í ¼öÀûÀ¸·Î ºÒ¾ÈÁ¤ÇÑ. ¿ì¸®´Â convex...

Approximation and Exact Algorithms for Minimum-Width Annuli and Shells (1999)

Pankaj K. Agarwal, Boris Aronov, Sariel Har-peled, Micha Sharir

Let S be a set of n points in R d . The "roundness" of S can be measured by computing the width ! = ! (S) of the thinnest spherical shell (or annulus in R 2 ) that contains S. This paper...

Efficient Hidden-Surface Removal in Theory and in Practice (1999)

T. M. Murali, T. M. Murali, Jeffrey Scott Vitter, Pankaj K. Agarwal, John F. Hughes

A central component of rendering is hiddent-surface removal. Given a set of objects, compute the scrne visible from the viewpoint as projected onto the image plane, we would like to compute the first...

Lower Bounds For Kinetic Planar Subdivisions (1999)

Pankaj K. Agarwal, Julien Basch, Mark De Berg, Leonidas J. Guibas, John Hershberger

We revisit the notion of kinetic eciency for non-canonically-dened discrete attributes of moving data, like binary space partitions and triangulations. Under very general computational models, we...

A Simple and Efficient Algorithm for High-Quality Line Labeling (1999)

Alexander Wolff, Lars Knipping, Marc Van Kreveld, Tycho Strijk, Pankaj K. Agarwal

The interest in algorithms that automatically place labels on maps, graphs, or diagrams has increased with the advance in type-setting technology and the amount of information to be visualized....

Emerging Challenges in Computational Topology (1999)

Marshall Bern, David Eppstein, Pankaj K. Agarwal, Nina Amenta, Paul Chew, Tamal Dey, ...

Here we present the results of the NSF-funded Workshop on Computational Topology, which met on June 11 and 12 in Miami Beach, Florida. This report identifies important problems involving both...

Geometric Range Searching and Its Relatives (1999)

Pankaj K. Agarwal, Jeff Erickson

From a theoretical point of view, range searching is now almost completely solved. The impact of general techniques developed for geometric range searching -- e-nets, 1/r cuttings, partition trees,...

Output-Sensitive Algorithms for Uniform Partitions of Points (1999)

Pankaj Agarwal Binay, Pankaj K. Agarwal, Binay K. Bhattacharya, Sandeep Sen, Or R

We consider the following one and two-dimensional bucketing problems: Given a set S of n points in R 1 or R 2 and a positive integer b, distribute the points of S into b equal-size buckets so that...

Pipes, Cigars, and Kreplach: The Union of Minkowski Sums in Three Dimensions (1999)

Geometric Range Searching and Its Relatives (1999)

Let\Omega be a set of pairwise-disjoint polyhedral obstacles in R 3 with a total of n vertices, and let B be a ball in R 3 . We show that the combinatorial complexity of the free configuration space...

Pankaj K. Agarwal, Jeff Erickson

. 1. Introduction HW Cl, Cl2 CS Pankaj K. Agarwal and Jeff Erickson Geometric Range Searching and Its Relatives Contemporary Mathematics c 0000 (copyright holder) Mathematics Subject Classification....

Approximation Algorithms for Bipartite and Non-Bipartite Matching in the Plane (1999)

Kasturi R. Varadarajan, Pankaj K. Agarwal

In the approximate Euclidean min-cost perfect matching problem, we are a given a set V of 2n points in the plane, and a real number " ? 0, and we want to pair up the points (into n pairs) so...

Covering Points by Strips in the Plane (1999)

Pankaj K. Agarwal, Cecilia M. Procopiuc

Given a set S of n points in R d and an integer k ? 0; we want to cover S by k strips so that the maximum width of a strip is minimized. This problem stems from the pattern-discovering class of...

Vertical decomposition of shallow levels in 3-dimensional arrangements and its applications (1999)

Pankaj K. Agarwal, Alon Efrat, Micha Sharir

Abstract Let F be a collection of n bivariate algebraic functions of constant maximum degree.We show that the combinatorial complexity of the vertical decomposition of the <= k-levelof the...

Pipes, Cigars, and Kreplach: The Union of Minkowski Sums in Three Dimensions (1999)

Pankaj K. Agarwal, Lars Arge, Jeff Erickson, Paulo G. Franciosa, Jeffrey Scott Vitter

and (1999)

194

Applicable and Robust Geometric Computing (1998)

Preparata, Franco P., Agarwal, Pankaj K., Tamassia, Roberto, Vitter, Jeffrey S., Goodrich, Michael T.

This research project is aimed at aimed at facilitating an effective technology transfer from computational geometry to the various applied fields to which it is relevant. Our technical contributions...

Box-Trees and R-Trees With Near-Optimal Query Time (1998)

Agarwal, Pankaj K., Berg, Mark De, Gudmundsson, Joachim, Hammar, Mikael, Haverkort, Herman J.

A box-tree is a bounding-volume hierarchy that uses axis-aligned boxes as bounding volumes The query complexity of a box-tree with respect to a given type of query is the maximum number of nodes...

On Levels in Arrangements of Lines, Segments, Planes, and Triangles (1998)

Agarwal, Pankaj K., Aronov, Boris, Sharir, Micha

We consider the problem of bounding the complexity of the k-th level in an arrangement of n curves or surfaces, a problem dual to, and extending the well-known k-set problem. (a) We review and...

On the Complexity of Many Faces in Arrangements of Circles (1998)

Agarwal, Pankaj K., Aronov, Boris, Sharir, Micha

We obtain improved bounds on the complexity of m distinct faces in an arrangement of n circles and in an arrangement of n unit circles. The bounds are worst-case tight for unit circles, and, for...

An On-Line Occlusio-Culling Algorithm for Fast Walkthrough in Urban Areas (1998)

Wang, Yusu, Agarwal, Pankaj K., Har-Peled, Sariel

We describe a fast algorithm to speed up rendering of scenes for walkthroughs in urban environments. Our occlusion culling algorithm takes advantage of temporal coherence in image space. As such,...

On the Number of Congruent Simplices in a Point Set (1998)

Agarwal, Pankaj K., Sharir, Micha

We derive improved bounds on the number of k-dimensional simplices spanned by a set of n points in R(sup d) that are congruent to a given k-simplex, for k < or = d - 1. Let f(sup d)(sub K)(n) be the...

Computational Geometry Column 34 (1998)

Agarwal, Pankaj K., O'Rourke, Joseph

Problems presented at the open-problem session of the 14th Annual ACM Symposium on Computational Geometry are listed.

Computing Many Faces in Arrangements of Lines and Segments. (1998)

Agarwal, Pankaj K., Matousek, Jirí, Schwarzkopf, Otfried

We present randomized algorithms for computing many faces in an arrangement of lines or of segments in the plane, which are considerably simpler and slightly faster than the previously known ones....

Constructing Levels in Arrangements and Higher Order Voronoi Diagrams. (1998)

Agarwal, Pankaj K., De Berg, Mark, Matousek, Jirí, Schwarzkopf, Otfried

We give simple randomized incremental algorithms for computing the Amk-level in an arrangement of n lines in the plane or in an arrangement of n planes in $\Reals^3$. The expected running time of our...

Label placement by maximum independent set in rectangles (1998)

Agarwal, Pankaj K., Kreveld, Marc Van, Suri, Subhash

Parametric and kinetic minimum spanning trees (1998)

Agarwal, Pankaj K., Eppstein, David, Guibas, Leonidas J., Henzinger, Monika R.

We consider the parametric minimum spanning tree problem, in which we are given a graph with edge weights that are linear functions of a parameter, and wish to computethe sequence of minimum spanning...

Davenport-Schinzel Sequences and Their Geometric Applications (1998)

I/O-efficient algorithms for contour-line extraction and planar graph blocking (1998)

An (n; s) Davenport-Schinzel sequence, for positive integers n and s, is a sequence composed of n distinct symbols with the properties that no two adjacent elements are equal, and that it does not...

Pankaj K. Agarwal, Lars Arge, T. M. Murali, Kasturi R. Varadarajan, Jeffrey Scott Vitter

For a polyhedral terrain \Sigma, the contour at z-coordinate h, denoted Ch, is defined to be the intersection of the plane z = h with \Sigma. In this paper, we study the contour-line extraction...

Label placement by maximum independent set in rectangles (1998)

Pankaj K. Agarwal, Marc Van Kreveld, Subhash Suri

Motivated by the problem of labeling maps, we investigate the problem of computing a large non-intersecting subset in a set of n rectangles in the plane. Our results are as follows. In O(n log n)...

Constructing levels in arrangements and higher order Voronoi diagrams (1998)

Pankaj K. Agarwal, Mark De Berg, Otfried Schwarzkopf

We give simple randomized incremental algorithms for computing the k-level in an arrangement of n hyperplanes in two- and three-dimensional space. The expected running time of our algorithms is...

Largest placement of one convex polygon inside another (1998)

Pankaj K. Agarwal, Nina Amenta, Micha Sharir

We show that the largest similar copy of a convex polygon P with m edges inside a convex polygon Q with n edges can be computed in O(mn 2 log n) time. We also show that the combinatorial complexity...

On levels in arrangements of lines, segments, planes, and triangles (1998)

Kinetic Binary Space Partitions for Intersecting Segments and Disjoint Triangles (Extended Abstract) (1998)

We consider the problem of bounding the complexity of the k-th level in an arrangement of n curves or surfaces, a problem dual to, and extending, the well-known k-set problem. (a) We review and...

P.K. Agarwal, Pankaj K. Agarwal, Je Erickson

) Pankaj K. Agarwal Jeff Erickson y Leonidas J. Guibas z Abstract We describe randomized algorithms for efficiently maintaining a binary space partition of continuously moving, possibly intersecting,...

Efficient algorithms for geometric optimization (1998)

Kinetic Binary Space Partitions for Intersecting Segments and Disjoint Triangles (1998)

We review the recent progress in the design of efficient algorithms for various problems in geometric optimization. We present several techniques used to attack these problems, such as parametric...

Pankaj K. Agarwal, Jeff Erickson, Leonidas J. Guibas

) Pankaj K. Agarwal Jeff Erickson y Leonidas J. Guibas z Abstract We describe randomized algorithms for efficiently maintaining a binary space partition of continuously moving, possibly intersecting,...

Efficient Searching with Linear Constraints (Extended Abstract) (1998)

Pankaj K. Agarwal, Lars Arge, Jeff Erickson, Paolo G. Franciosa, Jeffrey Scott Vitter

We show how to preprocess a set S of points in R d into an external memory data structure that efficiently supports linear-constraint queries. Each query is in the form of a linear constraint a...

Computing many faces in arrangements of lines and segments (1998)

Pankaj K. Agarwal, Jiri Matousek, Otfried Schwarzkopf

We present randomized algorithms for computing many faces in an arrangement of lines or of segments in the plane, which are considerably simpler and slightly faster than the previously known ones....

The Discrete 2-Center Problem (1998)

Pankaj K. Agarwal, Micha Sharir, Emo Welzl

We present an algorithm for computing the discrete 2-center of a set P of n points in the plane; that is, computing two congruent disks of smallest possible radius, centered at two points of P ,...

Efficient Searching with Linear Constraints (1998)

Pankaj K. Agarwal, Lars Arge, Jeff Erickson, Paolo G. Franciosa, Jeffrey Scott Vitter

We show how to preprocess a set S of points in R d into an external memory data structure that efficiently supports linear-constraint queries. Each query is in the form of a linear constraint x d a 0...

Surface Approximation and Geometric Partitions (1998)

Pankaj K. Agarwal, Subhash Suri

.<F3.842e+05> Motivated by applications in computer graphics, visualization, and scientific computation, we study the computational complexity of the following problem: given a...

Arrangements and Their Applications (1998)

Efficient Algorithms for Geometric Optimization (1998)

The arrangement of a finite collection of geometric objects is the decomposition of the space into connected cells induced by them. We survey combinatorial and algorithmic properties of arrangements...

I/O-Efficient Algorithms for Contour-line Extraction and Planar Graph Blocking (Extended Abstract) (1998)

We review the recent progress in the design of efficient algorithms for various problems in geometric optimization. We present several techniques used to attack these problems, such as parametric...

Pankaj K. Agarwal, Lars Arge, T. M. Murali, Kasturi R. Varadarajan, Jeffrey Scott Vitter

) Pankaj K. Agarwal Lars Arge y T. M. Murali z Kasturi R. Varadarajan x Jeffrey Scott Vitter -- Center for Geometric Computing Department of Computer Science Duke University Durham, NC 27708--0129...

Efficient Algorithms for Geometric Optimization (1998)

Constructing levels in arrangements and higher order Voronoi diagrams (1998)

We review the recent progress in the design of efficient algorithms for various problems in geometric optimization. We present several techniques used to attack these problems, such as parametric...

Pankaj K. Agarwal, Mark De Berg

Abstract. We give simple randomized incremental algorithms for computing the ≤k-level in an arrangement of n lines in the plane or in an arrangement of n planes in R 3. The expected running time of...

I/O-efficient algorithms for contour-line extraction and planar graph blocking (Extended Abstract) (1998)

Pankaj K. Agarwal, Lars Arge, T. M. Murali, Kasturi R. Varadarajan, Jeffrey Scott Vitter

For a polyhedral terrain, the contour at z-coordinate h, denoted Ch, is de ned to be the intersection of the plane z = h with. In this paper, we study the contour-line extraction problem, where we...

On levels in arrangements of lines, segments, planes, and triangles. Discrete Comput. Geom (1998)

Pankaj K. Agarwal, Boris Aronov, Timothy M. Chan, Micha Sharir

Abstract We consider the problem of bounding the complexity of the k-th level in an arrangement of n curves or surfaces, a problem dual to, and an extension of, the well-known k-set problem. Among...

EMPLOYMENT (1998)

Sathish Govindarajan, Advisor Pankaj, K. Agarwal, Worked Prof, Pankaj K. Agarwal

Computing many faces in arrangements of lines and segments (1998)

Pankaj K. Agarwal, Otfried Schwarzkopf

Abstract. We present randomized algorithms for computing many faces in an arrangement of lines or of segments in the plane, which are considerably simpler and slightly faster than the previously...

Exact and Approximation Algortihms for Clustering (Extended Abstract) (1998)

Extended Abstract, Pankaj K. Agarwal, Cecilia M. Procopiuc

) Pankaj K. Agarwal y Cecilia M. Procopiuc y Abstract In this paper we present an n O(k 1\Gamma1=d ) time algorithm for solving the k-center problem in R d , under L1 and L2 metrics. The algorithm...

Efficient algorithms for geometric optimization (1998)

Quasi-planar graphs have a linear number of edges. (1997)

We review the recent progress in the design of efficient algorithms for various problems in geometric optimization. We present several techniques used to attack these problems, such as parametric...

Range Searching. (1997)

Agarwal, Pankaj K.

Range searching is one of the central problems in computational geometry, because it arises in many applications and a wide variety of geometric problems can be formulated as a range-searching...

Agarwal, Pankaj K., Aronov, Boris, Pach, János, Pollack, Richard, Sharir, Micha

Computing envelopes in four dimensions with applications (1997)

Nonholonomic path planning for pushing a disk among obstacles (1997)

Abstract. Let F be a collection of nd-variate, possibly partially defined, functions, all algebraic of some constant maximum degree. We present a randomized algorithm that computes the vertices,...

Pankaj K. Agarwal, Jean-claude Latombe, Rajeev Motwani, Prabhakar Raghavan

We consider the path-planning problem for a robot pushing an object in an environment containing ob-stacles. This new variant of the classical robot path-planning problem has several interesting...

Cylindrical static and kinetic binary space partitions (1997)

Pankaj K. Agarwal, Leonidas J. Guibas, T. M. Murali, Jeffrey Scott Vitter

We describe the first known algorithm for efficiently maintaining a Binary Space Partition (BSP) for n continuously moving segments in the plane, whose interiors remain disjoint throughout the...

Practical Techniques for Constructing Binary Space Partitions for Orthogonal Rectangles (1997)

Pankaj K. Agarwal, T. M. Murali, Jeffrey Scott Vitter

We present the first systematic comparison of the performance of algorithms that construct Binary Space Partitions for orthogonal rectangles in R 3 . We compare known algorithms with our...

Approximating Shortest Paths on a Convex Polytope in Three Dimensions (1997)

Pankaj K. Agarwal, Sariel Har-peled, Micha Sharir, Kasturi R. Varadarajan

Given a convex polytope P with n faces in IR 3 , points s; t 2 @P , and a parameter 0 ! " 1, we present an algorithm that constructs a path on @P from s to t whose length is at most (1+ ")d...

The Discrete 2-Center Problem (1997)

Pankaj Agarwal Micha, Pankaj K. Agarwal, Pankaj K. Agarwal, Micha Sharir, Micha Sharir, Emo Welzl, ...

We present an algorithm for computing the discrete 2-center of a set P of n points in the plane; that is, computing two congruent disks of smallest possible radius, centered at two points of P ,...

Binary Space Partitions for Fat Rectangles (1997)

Pankaj K. Agarwal, Pankaj K. Agarwal, Edward F. Grove, Edward F. Grove, T. M. Murali, T. M. Murali, ...

We consider the practical problem of constructing binary space partitions (BSPs) for a set S of n orthogonal, non-intersecting, two-dimensional rectangles in R 3 such that the aspect ratio of each...

Line Transversals of Balls and Smallest Enclosing Cylinders in Three Dimensions (1997)

Pankaj K. Agarwal, Pankaj K. Agarwal, Boris Aronov, Boris Aronov, Micha Sharir, Micha Sharir

We establish a near-cubic upper bound on the complexity of the space of line transversals of a collection of n balls in three dimensions, and show that the bound is almost tight, in the worst case....

Geometric Range Searching and Its Relatives (1997)

Pankaj K. Agarwal, Pankaj K. Agarwal, Jeff Erickson, Jeff Erickson

this paper was supported by National Science Foundation Grant CCR93 -01259, by Army Research Office MURI grant DAAH04-96-1-0013, by a Sloan fellowship, by an NYI award and matching funds from Xerox...

Efficient Searching with Linear Constraints (1997)

Pankaj K. Agarwal, Lars Arge, Jeff Erickson, Paolo G. Franciosa, Jeffrey Scott Vitter

We show how to preprocess a set S of points in R^d into an external memory....

Efficient Searching with Linear Constraints (1997)

Pankaj K. Agarwal, Lars Arge, Jeff Erickson, Paolo G. Franciosa, Jeffrey Scott Vitter

We show how to preprocess a set S of points in R d into an external memory data structure that efficiently supports linear-constraint queries. Each query is in the form of a linear constraint x d a 0...

Exact and Approximation Algorithms for Clustering (1997)

Pankaj K. Agarwal, Cecilia M. Procopiuc

In this paper we present a n O(k 1\Gamma1=d ) time algorithm for solving the k-center problem in R d , under L1 and L 2 metrics. The algorithm extends to other metrics, and can be used to solve the...

On Levels in Arrangements of Lines, Segments, Planes, and Triangles (1997)

Pankaj K. Agarwal, Boris Aronov, Timothy M. Chan, Micha Sharir

We consider the problem of bounding the complexity of the k-th level in an arrangement of n curves or surfaces, a problem dual to, and an extension of, the well-known k-set problem. Among other...

Maintaining the Extent of a Moving Point Set (1997)

Pankaj K. Agarwal, Leonidas J. Guibas, John Hershberger, Eric Veach

Let S be a set of n moving points in the plane. We give new efficient and compact kinetic data structures for maintaining the diameter, width, and smallest area or perimeter bounding rectangle of the...

The Discrete 2-Center Problem (1997)

Pankaj K. Agarwal, Micha Sharir, Emo Welzl

We present an algorithm for computing the discrete 2-center of a set P of n points in the plane; that is, computing two congruent disks of smallest possible radius, centered at two points of P ,...

Computing Envelopes in Four Dimensions with Applications (1997)

Pankaj K. Agarwal, Pankaj K. Agarwal, Boris Aronov, Boris Aronov, Micha Sharir, Micha Sharir

Let F be a collection of n d-variate, possibly partially defined, functions, all algebraic of some constant maximum degree. We present a randomized algorithm that computes the vertices, edges, and...

I/O-Efficient Algorithms for Contour-line Extraction and Planar Graph Blocking (Extended Abstract) (1997)

Pankaj K. Agarwal, Lars Arge, T. M. Murali, Kasturi R. Varadarajan, Jeffrey S. Vitter

) Pankaj K. Agarwal Lars Arge y T. M. Murali z Kasturi R. Varadarajan x Jeffrey S. Vitter -- Center for Geometric Computing Department of Computer Science Duke University Durham, NC 27708--0129 July...

Practical techniques for constructing binary space partitions for orthogonal rectangles (1997)

Pankaj K. Agarwal, T. M. Murali, Jeffrey Scott Vitter

We present the first systematic comparison of the performance of algorithms that construct Binary Space Partitions for orthogonal rectangles in R³. We compare known algorithms with our...

Motion Planning for a Convex Polygon in a Polygonal Environment (1997)

We study the motion-planning problem for a convex m-gon P in a planar polygonal environment Q bounded by n edges. We give the first algorithm that constructs the entire free configuration space (the...

Range Searching (1997)

An Efficient Algorithm for Terrain Simplification (1997)

Range searching is one of the central problems in computational geometry, because it arises in many applications and a wide variety of geometric problems be formulated as a range searching-problem. A...

Pankaj K. Agarwal, Pavan K. Desikan

Given a set S of n points in ! 3 , sampled from an unknown bivariate function f(x; y) (i.e., for each point p 2 S, z p = f(x p ; y p )), a piecewise-linear function g(x; y) is called an...

Approximating Shortest Paths on a Nonconvex Polyhedron (1997)

Kasturi R. Varadarajan, Pankaj K. Agarwal

We present an approximation algorithm that, given a simple, possibly nonconvex polyhedron P with n vertices in R 3 , and two points s and t on its surface @P , constructs a path on @P between s and t...

Line Transversals of Balls and Smallest Enclosing Cylinders in Three Dimensions (1997)

Star unfolding of a polytope with applications (1997)

We establish a near-cubic upper bound on the complexity of the space of line transversals of a collection of n balls in three dimensions, and show that the bound is almost tight, in the worst case....

Pankaj K. Agarwal, Boris Aronov, Catherine A. Schevon

Abstract. We introduce the notion of a star unfolding of the surface P of a three-dimensional convex polytope with n vertices, and use it to solve several problems related to shortest paths on P. The...

Practical techniques for constructing binary space partitions for orthogonal rectangles (1997)

Pankaj K. Agarwal, T. M. Murali

We present the rst systematic comparison of the performance of algorithms that construct Binary Space Partitions for orthogonal rectangles in R 3. We compare known algorithms with our implementation...

Quasi-Planar Graphs Have a Linear Number of Edges (1996)

Agarwal, Pankaj K., Aronov, Boris, Pach, János, Pollack, Richard, Sharir, Micha

A graph is called quasi-planar if it can be drawn in the plane so that no three of its edges are pairwise crossing. It is shown that the maximum number of edges of a quasi-planar graph with n...

Quasi-Planar Graphs Have a Linear Number of Edges (1996)

Agarwal, Pankaj K., Aronov, Boris, Pach, János, Pollack, Richard, Sharir, Micha

A graph is called quasi-planar if it can be drawn in the plane so that no three of its edges are pairwise crossing. It is shown that the maximum number of edges of a quasi-planar graph with n...

Selection in monotone matrices and computing kth nearest neighbors (1996)

Agarwal, Pankaj K., Sen, Sandeep

An m x n matrix A=(ai j),1,i,m and 1,j

Quasi-Planar Graphs Have a Linear Number of Edges (1996)

Agarwal, Pankaj K., Aronov, Boris, Pach, János, Pollack, Richard, Sharir, Micha

A graph is called quasi-planar if it can be drawn in the plane so that no three of its edges are pairwise crossing. It is shown that the maximum number of edges of a quasi-planar graph with n...

The overlay of lower envelopes and its applications (1996)

Micha Sharir, Micha Sharir, Pankaj K. Agarwal, Pankaj K. Agarwal, Pankaj K. Agarwal, Otfried Schwarzkopf, ...

Sharir x Let F and G be two collections of a total of n bivariate algebraic functions of constant maximum degree. The minimization diagrams of F, G are the planar maps obtained by the xy-projections...

Binary Space Partitions for Fat Rectangles (1996)

Pankaj K. Agarwal, Edward F. Grove, T. M. Murali, Jeffrey Scott Vitter

We consider the practical problem of constructing binary space partitions (BSPs) for a set S of n orthogonal, non-intersecting, two-dimensional rectangles in R 3 such that the aspect ratio of each...

Efficient randomized algorithms for some geometric optimization problems (1996)

Pankaj K. Agarwal, Pankaj K. Agarwal, Micha Sharir, Micha Sharir

has been supported by NSF Grants CCR-91-22103 and CCR-93-11127, by a Max-Planck Research

Strategic Directions in Computational Geometry (1996)

Roberto Tamassia, Roberto Tamassia (editor, Pankaj K. Agarwal, Nancy Amato, Danny Z. Chen, David Dobkin, ...

ing with credit is permitted. To copy otherwise, to republish, to post on servers, to redistribute to lists, or to use any component of this work in other works, requires prior specific permission...

Vertical Decomposition of Shallow Levels in 3-Dimensional Arrangements and Its Applications (1996)

Pankaj K. Agarwal, Alon Efrat, Micha Sharir

Let F be a collection of n bivariate algebraic functions of constant maximum degree. We show that the combinatorial complexity of the vertical decomposition of the k-level of the arrangement A(F) is...

Pankaj K. Agarwal (1996)

Ga Rw Al, Pankaj K. Agarwal, Pankaj K. Agarwal

INTRODUCTION Range searching is one of the central problems in computational geometry, because it arises in many applications and a wide variety of geometric problems can be formulated as a...

Largest Placement of One Convex Polygon inside Another (1996)

Pankaj Agarwal Nina, Pankaj Agarwal, Pankaj K. Agarwal, Pankaj K. Agarwal, Nina Amenta, ...

We show that the largest similar copy of a convex polygon P with m edges inside a convex polygon Q with n edges can be computed in O(mn 2 log n) time. We also show that the combinatorial complexity...

The Overlay of Lower Envelopes and its Applications (1996)

Pankaj K. Agarwal, Otfried Schwarzkopf, Micha Sharir

Let F and G be two collections of a total of n (possibly partially-defined) bivariate algebraic functions of constant maximum degree. The minimization diagrams of F , G are the planar maps obtained...

Approximation Algorithms for Curvature-Constrained Shortest Paths (1996)

Hongyan Wang, Pankaj K. Agarwal

Let B be a point robot in the plane, whose path is constrained to have curvature of at most 1, and let\Omega be a set of polygonal obstacles with n vertices. We study the collisionfree, optimal...

Largest Placement of One Convex Polygon inside Another (1996)

Pankaj Agarwal Nina, Pankaj K. Agarwal, Nina Amenta, Micha Sharir

We show that the largest similar copy of a convex polygon P with m edges inside a convex polygon Q with n edges can be computed in O(mn 2 log n) time. We also show that the combinatorial complexity...

Surface Approximation and Geometric Partitions (1996)

Pankaj K. Agarwal, Subhash Suri

Motivated by applications in computer graphics, visualization, and scientific computation, we study the computational complexity of the following problem: Given a set S of n points sampled from a...

On Levels in Arrangements of Lines, Segments, Planes, and Triangles (1996)

Binary Space Partitions for Fat Rectangles (1996)

We consider the problem of bounding the complexity of the k-th level in an arrangement of n curves or surfaces, a problem dual to, and extending, the well-known k-set problem. (a) We review and...

Pankaj K. Agarwal, Edward F. Grove, T. M. Murali, Jeffrey Scott Vitter

We consider the practical problem of constructing binary space partitions (BSPs) for a set S of n orthogonal, nonintersecting, two-dimensional rectangles in IR 3 such that the aspect ratio of each...

Approximating Shortest Paths on a Convex Polytope in Three Dimensions (1996)

Pankaj K. Agarwal, Sariel Har-peled, Micha Sharir, Kasturi R. Varadarajan

Given a convex polytope P with n faces in IR 3 , points s; t 2 @P , and a parameter 0 ! " 1, we present an algorithm that constructs a path on @P from s to t whose length is at most (1+")d...

Approximation Algorithms for Curvature-Constrained Shortest Paths (1996)

Hongyan Wang, Hongyan Wang, Pankaj K. Agarwal, Pankaj K. Agarwal

Let B be a point robot in the plane, whose path is constrained to have curvature of at most 1, and let\Omega be a set of polygonal obstacles with n vertices. We study the collision-free, optimal...

Approximation Algorithms for Curvature-Constrained Shortest Paths (1996)

Hongyan Wang, Pankaj K. Agarwal

Let B be a point robot in the plane, whose path is constrained to have curvature of at most 1, and let\Omega be a set of polygonal obstacles with n vertices. We study the collision-free, optimal...

The Overlay of Lower Envelopes and its Applications (1996)

Pankaj Agarwal, Pankaj K. Agarwal, Otfried Schwarzkopf, Otfried Schwarzkopf, Micha Sharir, Micha Sharir

Let F and G be two collections of a total of n bivariate algebraic functions of constant maximum degree. The minimization diagrams of F , G are the planar maps obtained by the xy-projections of the...

Largest Placements and Motion Planning of a Convex Polygon (1996)

Pankaj K. Agarwal, Nina Amenta, Boris Aronov, Micha Sharir

We study two problems involving collision-free placements of a convex m-gon P in a planar polygonal environment: (i) We first show that the largest similar copy of P inside another convex polygon Q...

Combinatorial Geometry (1995)

Pach, János, Agarwal, Pankaj K.

Algorithmic techniques for geometric optimization (1995)

Davenport-Schinzel Sequences and Their Geometric Applications (1995)

Pankaj K. Agarwal, Pankaj K. Agarwal, Micha Sharir, Micha Sharir

An (n; s) Davenport--Schinzel sequence, for positive integers n and s, is a sequence composed of n symbols with the properties that no two adjacent elements are equal, and that it does not contain,...

Generating Levels of Detail for Large-Scale Polygonal Models (1995)

Amitabh Varshney, Pankaj K. Agarwal, Frederick P. Brooks, William V. Wright, ...

We present an efficient algorithm for generating various levels-of-detail approximations for a given polygonal model. Our algorithm guarantees that all points of an approximation are within a...

Vertical Decomposition of Shallow Levels in 3-Dimensional Arrangements and Its Applications (1995)

Alon Efrat, Micha Sharir, Pankaj K. Agarwal, Pankaj K. Agarwal

Let F be a collection of n bivariate algebraic functions of constant maximum degree. We show that the combinatorial complexity of the vertical decomposition of the k-level of the arrangement A(F) is...

Pankaj K. Agarwal (1995)

Boris Aronov Anos, Pankaj K. Agarwal, Boris Aronov, Richard Pollack, Micha Sharir

A graph is called quasi-planar if it can be drawn in the plane so that no three of its edges are pairwise crossing. It is shown that the maximum number of edges of a quasi-planar graph with n...

Linear approximation of simple objects (1995)

Kasturi R. Varadarajan, Pankaj K. Agarwal

Let P = fP 1; P 2; : : : ; Pm g be a set of m convex polygons in the plane with a total number of n vertices, and for 1 i m, let w i 2 R be a weight associated with P i. The weighted distance between...

Algorithmic Techniques for Geometric Optimization (1995)

Efficient Randomized Algorithms for Some Geometric Optimization Problems (1995)

Linear Programming In this section we present an abstract framework that captures both linear programming and many other geometric optimization problems, including computing smallest enclosing balls...

Constructing Levels in Arrangements and Higher Order Voronoi Diagrams (1995)

In this paper we first prove the following combinatorial bound, concerning the complexity of the vertical decomposition of the minimization diagram of trivariate functions: Let F be a collection of n...

Otfried Schwarzkopf, Pankaj K. Agarwal, Jiri Matousek, Pankaj K. Agarwal, Mark De Berg, Mark De Berg

We give simple randomized incremental algorithms for computing the k-level in an arrangement of n hyperplanes in two- and three-dimensional space. The expected running time of our algorithms is O(nk...

Algorithmic techniques for geometric optimization (1995)

Pankaj K. Agarwal, Sandeep Sen

Abstract. We review the recent progress in the design of e cient algorithms for various problems in geometric optimization. The emphasis in this survey is on the techniques used to attack these...

and (1994)

An m � n matrix A �Ž a. i, j, 1�i�m and 1 � j � n, is called a totally monotone matrix if for all i 1, i 2, j 1, j 2, satisfying 1 � i1�i2�m, 1�j1 �j2�n. a �a �a �a. i,...

The Overlay ofLower Envelopes and its Applications (1994)

Pankaj K. Agarwal, Otfried Schwarzkopf, Micha Sharir

Let F and G be two collections of a total of n bivariate algebraic functions of constant maximum degree. The minimization diagrams of F, G are the planar maps obtained by the xy-projections of the...

Applications of parametric searching in geometric optimization (1994)

Surface approximation and geometric partitions (1994)

z Sivan Toledo x

Pankaj K. Agarwal, Subhash Suri

Motivated by applications in computer graphics, visualization, and scientific computation, we study the computational complexity of the following problem: Given a set S of n points sampled from a...

Computing depth orders and related problems (1994)

Pankaj K. Agarwal, Pankaj K. Agarwal, Matthew J. Katz, Matthew J. Katz, Micha Sharir, Micha Sharir

Let K be a set of n non-intersecting objects in 3-space. A depth order of K, if exists, is a linear order! of the objects in K such that if K;L 2 K and K lies vertically below L then K! L. We present...

Applications of parametric searching in geometric optimization (1994)

Pankaj K. Agarwal, Micha Sharir, Sivan Toledo

Surface Approximation and Geometric Partitions (1994)

Pankaj K. Agarwal, Pankaj K. Agarwal, Subhash Suri, Subhash Suri

Motivated by applications in computer graphics, visualization, and scientific computation, we study the computational complexity of the following problem: Given a set S of n points sampled from a...

On Range Searching with Semialgebraic Sets (1994)

Pankaj K. Agarwal, Pankaj K. Agarwal, Jirí Matousek

Let P be a set of n points in R d (where d is a small fixed positive integer), and let \Gamma be a collection of subsets of R d , each of which is defined by a constant number of bounded degree...

Computing Depth Orders and Related Problems (1994)

Pankaj K. Agarwal, Matthew J. Katz, Micha Sharir

Let K be a set of n non-intersecting objects in 3-space. A depth order of K, if exists, is a linear order ! of the objects in K such that if K;L 2 K and K lies vertically below L then K ! L. We...

Computing Many Faces in Arrangements of Lines and Segments (1994)

Jiri Matousek, Pankaj K. Agarwal, Otfried Schwarzkopf, Otfried Schwarzkopf

We present randomized algorithms for computing many faces in an arrangement of lines or of segments in the plane, which are considerably simpler and slightly faster than the previously known ones....

Connected component and simple polygon intersection searching (1993)

Pankaj K. Agarwal, Marc Van Kreveld

Efficient data structures are given for the following two query problems: preprocess a set P of simple polygons with a total of n edges, so that all polygons of P intersected by a query segment can...

An Efficient Multi-Dimensional Searching Technique and its Applications (1993)

Sivan Toledo, Pankaj K. Agarwal, Pankaj K. Agarwal, Micha Sharir, Micha Sharir

This paper describes an improved algorithm for the multi-dimensional searching problem introduced by Megiddo. As a result, we obtain a d O(d) n time deterministic algorithms for linear programming in...

Ray Shooting Amidst Convex Polyhedra and Polyhedral Terrains in Three Dimensions (1993)

Pankaj K. Agarwal, Pankaj K. Agarwal, Micha Sharir, Micha Sharir

We consider the problem of ray shooting in a 3-dimensional scene consisting of m (possibly intersecting) convex polyhedra or polyhedral terrains with a total of n faces, i.e., we want to preprocess...

On Stabbing Lines for Convex Polyhedra in 3D (1993)

Pankaj K. Agarwal, Pankaj K. Agarwal

Given a set B of convex polyhedra in R 3 , a line ` in R 3 is called a stabbing line for B if it intersects all polyhedra of B. This paper presents an upper bound of O(n 3 log n) on the complexity of...

Star Unfolding of a Polytope with Applications (1993)

Pankaj K. Agarwal, Pankaj K. Agarwal, Joseph O'Rourke, Boris Aronov, Boris Aronov, Catherine A. Schevon, ...

We define the notion of a star unfolding of the surface P of a convex polytope with n vertices, and use it to solve several problems related to shortest paths on P. The first algorithm computes the...

Can Visibility Graphs Be Represented Compactly? (1993)

Pankaj K. Agarwal, Pankaj K. Agarwal, Noga Alon, Noga Alon, Boris Aronov, Boris Aronov, ...

We consider the problem of representing the visibility graph of line segments as a union of cliques and bipartite cliques. Given a graph G, a family G = fG 1 ; G 2 ; : : : ; G k g is called a clique...

On the Number of Views of Polyhedral Terrains (1993)

Pankaj K. Agarwal, Pankaj K. Agarwal, Micha Sharir, Micha Sharir

We show that the number of topologically-different orthographic views of a polyhedral terrain with n edges is O(n 5+" ), and that the number of topologically-different perspective views of such...

Line Stabbing Bounds in Three Dimensions (1993)

Pankaj K. Agarwal, Boris Aronov, Subhash Suri

Let S be a set of (possibly degenerate) triangles in ! 3 whose interiors are disjoint. A triangulation of ! 3 with respect to S, denoted by T (S), is a simplicial complex in which the interior of no...

Connected Component and Simple Polygon Intersection Searching (1993)

Marc Kreveld, Pankaj Agarwal, Pankaj K. Agarwal, Marc Van Kreveld

Efficient data structures are given for the following two query problems: preprocess a set P of simple polygons with a total of n edges, so that all polygons of P intersected by a query segment can...

Implicit Point Location in Arrangements of Line Segments, with an Application to Motion Planning (1992)

Marc Van Kreveld, Pankaj K. Agarwal, Pankaj K. Agarwal, Marc Van Kreveld

Let S be a set of n (possibly intersecting) line segments in the plane. We show that the arrangement of S can be stored implicitly into a data structure of size O(n log 2 n) so that the following...

Applications of Parametric Searching in Geometric Optimization (1992)

Sivan Toledo, Pankaj K. Agarwal, Pankaj K. Agarwal, Micha Sharir, Micha Sharir

We present several applications in computational geometry of Megiddo's parametric searching technique. These applications include: (1) Finding the minimum Hausdorff distance in the Euclidean...

Off-line dynamic maintenance of the width of a planar point set (1991)

Intersection and decomposition algorithms for arrangements of curves in the plane / (1989)

Agarwal, P.K. and M. Sharir, Off-line dynamic maintenance of the width of a planar point set, Computational Geometry: Theory and Applications 1 (1991) 65-78. In this paper we present an efficient...

Agarwal, Pankaj K.

Typescript.

Motion Planning of a Ball Amid Segments in Three Dimensions