The Complexity of Bisectors and Voronoi Diagrams on Realistic Terrains (2009)
Boris Aronov, Mark De Berg, Shripad Thite
Abstract. We prove tight bounds on the complexity of bisectors and Voronoi diagrams on so-called realistic terrains, under the geodesic distance. In particular, if n denotes the number of triangles...
Graduated 1 st rank in University; Awarded D.Y. Patil Gold Medal Experience (2009)
Conduct independent research program in algorithms for combinatorial problems in computational
CACHE-OBLIVIOUS SELECTION IN SORTED X + Y MATRICES (2009)
Abstract. Let X[0..n − 1] and Y [0..m − 1] be two sorted arrays, and define the m × n matrix A by A[j][i] = X[i] + Y [j]. Frederickson and Johnson [7] gave an efficient algorithm for selecting...
WALKING YOUR DOG IN THE WOODS IN POLYNOMIAL TIME (2009)
Erin Wolf Chambers, Éric Colin, De Verdière, Jeff Erickson, Sylvain Lazard, Francis Lazarus, ...
Abstract. The Fréchet distance between two curves in the plane is the minimum length of a leash that allows a dog and its owner to walk along their respective curves, from one end to the other,...
I/O-Efficient Map Overlay and Point Location in Low-Density Subdivisions ⋆ (2009)
Mark De Berg, Herman Haverkort, Shripad Thite, Laura Toma
Abstract. We present improved and simplified i/o-efficient algorithms for two problems on planar low-density subdivisions, namely map overlay and point location. More precisely, we show how to...
Adaptive spacetime meshing for discontinuous Galerkin methods (2009)
Spacetime-discontinuous Galerkin (SDG) finite element methods are used to solve hyperbolic spacetime partial differential equations (PDEs) to accurately model wave propagation phenomena arising in...
Cache-oblivious selection in sorted X+Y matrices (2008)
Let X[0 . . n - 1] and Y[0 . . m - 1] be two sorted arrays, and define the m x n matrix A by A[j][i] = X[i] + Y[j]. Frederickson and Johnson [G.N. Frederickson, D.B. Johnson. Generalized selection...
Walking Your Dog in the Woods in Polynomial Time (2008)
Erin W. Chambers, Éric Colin, Verdière Jeff, Erickson Sylvain Lazard, Francis Lazarus, Shripad Thite
Given two input curves, the Fréchet distance, sometimes called the dog-leash distance, between them is defined as the minimum length of a leash required to connect a dog and its owner as they walk...
Abstract I/O-Efficient Map Overlay and Point Location in Low-Density Subdivisions (2008)
Mark Berg, Herman Haverkort, Shripad Thite, Laura Toma
We present improved and simplified i/o-efficient algorithms for two problems on planar low-density subdivisions, namely map overlay and point location. More precisely, we show how to preprocess a...
Distance-2 edge coloring is NPcomplete (2008)
Jeff Erickson, Shripad Thite, David Bunde
Let G be a simple, undirected graph. We say that two edges of G are within distance 2 of each other if either they are adjacent or there is some other edge that is adjacent to both of them. A...
Instructor Jeff Erickson, Fall Chris Neihengen, Ekta Manaktala, Nick Hurlburt, Spring Brian Ensink, Chris Neihengen, ...
This work may be freely copied and distributed. It may not be sold for more than the actual cost of reproduction. This work is distributed under a Creative Commons license; see
ADAPTIVE SPACETIME MESHING FOR DISCONTINUOUS GALERKIN METHODS (2008)
Abstract. Spacetime-discontinuous Galerkin (SDG) finite element methods are used to solve hyperbolic spacetime partial differential equations (PDEs) to accurately model wave propagation phenomena...
ADAPTIVE SPACETIME MESHING FOR DISCONTINUOUS GALERKIN METHODS (2008)
Abstract. Spacetime-discontinuous Galerkin (SDG) finite element methods are used to compute numerical solutions of hyperbolic spacetime partial differential equations (PDEs) for accurately modeling...
TIGHT BOUNDS ON THE COMPLEXITY OF RECOGNIZING ODD-RANKED ELEMENTS (2008)
Abstract. Let S = 〈s1, s2, s3,..., sn 〉 be a given vector of n distinct real numbers. The rank of z ∈ R with respect to S is defined as the number of elements si ∈ S such that si ≤ z. We...
Strong Edge Coloring for Channel Assignment in Wireless Radio Networks (2008)
Madhav V. Marathe, Shripad Thite, Sunil Thulasidasan
Abstract — We give efficient sequential and distributed approximation algorithms for strong edge coloring graphs modeling wireless networks. Strong edge coloring is equivalent to computing a...
IEEE TRANSACTIONS ON ROBOTICS 1 Capturing a Convex Object with Three Discs (2008)
Jeff Erickson, Shripad Thite, Fred Rothganger, Jean Ponce Fellow
Abstract — This paper addresses the problem of capturing an arbitrary convex object P in the plane with three congruent disc-shaped robots. Given two stationary robots in contact with P, we...
Distance-2 edge coloring is NPcomplete (2008)
Jeff Erickson, Shripad Thite, David P. Bunde
We prove that it is NP-complete to determine whether there exists a distance-2 edge coloring (strong edge coloring) with 5 colors of a bipartite 2-inductive graph with girth 6 and maximum degree 3....
I/O-Efficient Map Overlay and Point Location in Low-Density Subdivisions ∗ (2008)
Mark Berg, Herman Haverkort, Shripad Thite, Laura Toma
We present improved and simplified i/o-efficient algorithms for two problems on planar lowdensity subdivisions, namely map overlay and point location. More precisely, we show how to preprocess a...
Walking Your Dog in the Woods in Polynomial Time (2008)
Wolf Chambers, Erin, Colin De Verdire, Eric, Erickson, Jeff, Lazard, Sylvain, Lazarus, Francis, Thite, Shripad
The Frechet distance between two curves in the plane is the minimum length of a leash that allows a dog and its owner to walk along their respective curves, from one end to the other, without...
Walking Your Dog in the Woods in Polynomial Time (2008)
Wolf Chambers, Erin, Colin De Verdire, Eric, Erickson, Jeff, Lazard, Sylvain, Lazarus, Francis, Thite, Shripad
The Frechet distance between two curves in the plane is the minimum length of a leash that allows a dog and its owner to walk along their respective curves, from one end to the other, without...
WALKING YOUR DOG IN THE WOODS IN POLYNOMIAL TIME 1 (2008)
Erin Wolf Chambers, Éric Colin, De Verdière, Jeff Erickson, Sylvain Lazard, Francis Lazarus, ...
Abstract. The Fréchet distance between two curves in the plane is the minimum length of a leash that allows a dog and its owner to walk along their respective curves, from one end to the other,...
c Copyright by Shripad Thite, 2001 (2007)
The Hierarchical Memory Model (HMM) of computation is similar to the standard Random Access Machine (RAM) model except that the HMM has a non-uniform memory organized in a hierarchy of levels...
Counting Complexity Classes (2007)
The counting complexity classes are dened in terms of the number of accepting computation paths of nondetereministic polynomial-time Turing machines. They are, therefore, the counting versions of...
Parametric Search for Geometric Optimization CS 497 SHP: Fall 2000 (2007)
Let f(x) be a monotone nondecreasing function of x, i.e., y> x =) f(y) f(x).
Counting Complexity Classes (2007)
The counting complexity classes are defined in terms of the number of accepting computation paths of nondetereministic polynomial-time Turing machines. They are, therefore, the counting versions of...
1.1 Subspaces Points in P (2007)
\All geometry is linear algebra." (with apologies to Arthur Cayley) 1 A model of projective geometry
Instructor Je Erickson, Spring Mitch Harris, Shripad Thite, Stephen Wright
This work may be freely copied and distributed. It may not be sold for more than the actual cost of reproduction. For the most recent edition, see
Reza Abedi, Shuo-heng Chung, Jeff Erickson, Yong Fan, Michael Garl, Damrong Guoy, ...
We propose a new algorithm for constructing finite-element meshes suitable for spacetime discontinuous Galerkin solutions of linear hyperbolic PDEs. Given a triangular mesh of some planar domain Ω...
WALKING YOUR DOG IN THE WOODS IN POLYNOMIAL TIME 1 (2007)
Erin Wolf Chambers, Éric Colin, De Verdière, Jeff Erickson, Sylvain Lazard, Francis Lazarus, ...
Abstract. The Fréchet distance between two curves in the plane is the minimum length of a leash that allows a dog and its owner to walk along their respective curves, from one end to the other,...
On Covering a Graph Optimally with Induced Subgraphs (2006)
We consider the problem of covering a graph with a given number of induced subgraphs so that the maximum number of vertices in each subgraph is minimized. We prove NP-completeness of the problem,...
Meshing in 2D×time for front-tracking DG methods (2005)
Shripad Thite, Jeff Erickson, Shuo-heng Chung, Reza Abedi Jay
Spacetime discontinuous Galerkin (SDG) finite element methods are used to solve hyperbolic PDEs describing wavelike phenomena, such as fluid flow. In front-tracking SDG methods, the inclined facets...
Adaptive spacetime meshing in 2D×time for nonlinear and anisotropic media (2005)
Shripad Thite, Shuo-heng Chung, Jeff Erickson, Robert Haber
Scientists and engineers use hyperbolic partial differential equations (PDEs) to model wave propagation phenomena. Anisotropy of the transmitting medium can cause waves to propagate asymmetrically,...
Atkins, Karla, Barrett, Chris, Homan, Christopher, Marathe, Achla, Marathe, Madhav, Thite, Shripad
"Marketecture: A Simulation-Based Framework for Studying Experimental Deregulated Power Market," Proceedings of the 6th IAEE European Energy Conference. Held at ETH Zurich: 2-3 September 2004
Adaptive discontinuous galerkin method for elastodynamics on unstructured spacetime grids (2004)
Reza Abedi, Shuo-heng Chung, Yong Fan, Shripad Thite, Jeff Erickson, Robert B. Haber
Summary We present an adaptive spacetime discontinuous Galerkin (SDG) method for linearized elastodynamics. The SDG method uses a simple Bubnov-Galerkin projection that delivers stable and...
Hari Balakrishnan, Christopher L. Barrett, Madhav V. Marathe, Shripad Thite
Abstract—We consider the problem of determining the maximum capacity of the media access (MAC) layer in wireless ad hoc networks. Due to spatial contention for the shared wireless medium, not all...
Karla Atkins, Chris Barrett, Madhav Marathe, Christopher M. Homan, Shripad Thite, Achla Marathe
In this paper, we present MARKETECTURE, an agent-based, microeconomic, scalable model for studying deregulated power markets. Features that distinguish it from previously studied models include: the...
Spacetime Meshing for Discontinuous Galerkin Methods (2004)
Spacetime discontinuous Galerkin (DG) methods are used to solve hyperbolic partial di#erential equations (PDEs) describing wavelike mechanical phenomena. Given a simplicially meshed space domain M ,...
Efficient Spacetime Meshing With Nonlocal (2004)
Cone Constraints Shripad, Shripad Thite
Spacetime Discontinuous Galerkin (DG) methods are used to solve hyperbolic PDEs describing wavelike physical phenomena. When the PDEs are nonlinear, the speed of propagation of the phenomena, called...
Capturing a convex object with three discs (2003)
Jeff Erickson, Shripad Thite, Fred Rothganger, Jean Ponce
Abstract — This paper addresses the problem of capturing an arbitrary convex object P in the plane with three congruent discshaped robots. Given two stationary robots in contact with P, we...
Capturing a convex object with three discs (2003)
Je Erickson, Shripad Thite, Fred Rothganger, Jean Ponce
Abstract: This paper addresses the problem of capturing an arbitrary convex object P in the plane with three congruent disc-shaped robots. Given two stationary robots in contact with P, we...
Parametric Search for Geometric Optimization (2000)
Introduction Let f(x) be a monotone nondecreasing function of x, i.e., y > x =) f(y) f(x). Problem: Determine x = supfx : f(x) = 0g. Can be generalized to nding, say, the maximum of a concave...