98 citations · 365 across the 61 of their papers we have counts for
23 papers · 1 filter
Trajectory Minimum Touching Ball
Jeff M. Phillips, Jens Kristian Refsgaard Schou
We present algorithms to find the minimum radius sphere that intersects every trajectory in a set of trajectories composed of at most line segments each. When , we can…
Classifying Spatial Trajectories
Hasan Pourmahmood-Aghababa, Jeff M. Phillips
We provide the first comprehensive study on how to classify trajectories using only their spatial representations, measured on 5 real-world data sets. Our comparison considers 20 d…
Orientation-Preserving Vectorized Distance Between Curves
Jeff M. Phillips, Hasan Pourmahmood-Aghababa
We introduce an orientation-preserving landmark-based distance for continuous curves, which can be viewed as an alternative to the \Frechet or Dynamic Time Warping distances. This…
Sketched MinDist
Jeff M. Phillips, Pingfan Tang
We consider sketch vectors of geometric objects through the \mindist function \[ v_i(J) = \inf_{p \in J} \|p-q_i\| \] for from a point set . Collecting the vecto…
The VC Dimension of Metric Balls under Fréchet and Hausdorff Distances
Anne Driemel, André Nusser, Jeff M. Phillips +1
The Vapnik-Chervonenkis dimension provides a notion of complexity for systems of sets. If the VC dimension is small, then knowing this can drastically simplify fundamental computat…
Practical Low-Dimensional Halfspace Range Space Sampling
Michael Matheny, Jeff M. Phillips
We develop, analyze, implement, and compare new algorithms for creating -samples of range spaces defined by halfspaces which have size sub-quadratic in …
Computing Approximate Statistical Discrepancy
Michael Matheny, Jeff M. Phillips
Consider a geometric range space where each data point has two or more values (say and ). Also consider a function defined on any subset $A \…
Simple Distances for Trajectories via Landmarks
Jeff M. Phillips, Pingfan Tang
We develop a new class of distances for objects including lines, hyperplanes, and trajectories, based on the distance to a set of landmarks. These distances easily and interpretabl…
Nearest-Neighbor Searching Under Uncertainty II
Pankaj K. Agarwal, Boris Aronov, Sariel Har-Peled +3
Nearest-neighbor search, which returns the nearest neighbor of a query point in a set of points, is an important and widely studied problem in many fields, and it has wide range of…
Coresets and Sketches
Jeff M. Phillips
Geometric data summarization has become an essential tool in both geometric approximation algorithms and where geometry intersects with big data problems. In linear or near-linear…
Subsampling in Smoothed Range Spaces
Jeff M. Phillips, Yan Zheng
We consider smoothed versions of geometric range spaces, so an element of the ground set (e.g. a point) can be contained in a range with a non-binary value in . Similar noti…
Geometric Inference on Kernel Density Estimates
Jeff M. Phillips, Bei Wang, Yan Zheng
We show that geometric inference of a point cloud can be calculated by examining its kernel density estimate with a Gaussian kernel. This allows one to consider kernel density esti…
Range Counting Coresets for Uncertain Data
Amirali Abdullah, Samira Daruki, Jeff M. Phillips
We study coresets for various types of range counting queries on uncertain data. In our model each uncertain point has a probability density describing its location, sometimes defi…
Geometric Computations on Indecisive and Uncertain Points
Allan Jorgensen, Maarten Löffler, Jeff M. Phillips
We study computing geometric problems on uncertain points. An uncertain point is a point that does not have a fixed location, but rather is described by a probability distribution.…
epsilon-Samples of Kernels
Jeff M. Phillips
We study the worst case error of kernel density estimates via subset approximation. A kernel density estimate of a distribution is the convolution of that distribution with a fixed…
A Gentle Introduction to the Kernel Distance
Jeff M. Phillips, Suresh Venkatasubramanian
This document reviews the definition of the kernel distance, providing a gentle introduction tailored to a reader with background in theoretical computer science, but limited expos…
Stability of epsilon-Kernels
Pankaj K. Agarwal, Jeff M. Phillips, Hai Yu
Given a set P of n points in |R^d, an eps-kernel K subset P approximates the directional width of P in every direction within a relative (1-eps) factor. In this paper we study the…
Comparing Distributions and Shapes using the Kernel Distance
Sarang Joshi, Raj Varma Kommaraju, Jeff M. Phillips +1
Starting with a similarity function between objects, it is possible to define a distance metric on pairs of objects, and more generally on probability distributions over them. Thes…
Computing Hulls And Centerpoints In Positive Definite Space
P. Thomas Fletcher, John Moeller, Jeff M. Phillips +1
In this paper, we present algorithms for computing approximate hulls and centerpoints for collections of matrices in positive definite space. There are many applications where the…
Shape Fitting on Point Sets with Probability Distributions
Maarten Loffler, Jeff M. Phillips
A typical computational geometry problem begins: Consider a set P of n points in R^d. However, many applications today work with input that is not precisely known, for example when…
An Efficient Algorithm for 2D Euclidean 2-Center with Outliers
Pankaj K. Agarwal, Jeff M. Phillips
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 whe…
Algorithms for eps-approximations of Terrains
Jeff M. Phillips
Consider a point set D with a measure function w : D -> R. Let A be the set of subsets of D induced by containment in a shape from some geometric family (e.g. axis-aligned rectangl…
The Hunting of the Bump: On Maximizing Statistical Discrepancy
Deepak Agarwal, Jeff M. Phillips, Suresh Venkatasubramanian
Anomaly detection has important applications in biosurveilance and environmental monitoring. When comparing measured data to data drawn from a baseline distribution, merely, findin…