Source author record

Sue Whitesides

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Computational Geometry Data Structures and Algorithms Databases Discrete Mathematics math.MG

Catalog footprint

Research overview

12works

5topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

The Hamiltonian Path Graph is Connected for Simple $s,t$ Paths in Rectangular Grid Graphs

A \emph{simple} $s,t$ path $P$ in a rectangular grid graph $\mathbb{G}$ is a Hamiltonian path from the top-left corner $s$ to the bottom-right corner $t$ such that each \emph{internal} subpath of $P$ with both endpoints $a$ and $b$ on the boundary of $\mathbb{G}$ has the minimum number of bends needed to travel from $a$ to $b$ (i.e., $0$ , $1$ , or $2$ bends, depending on whether $a$ and $b$ are on opposite, adjacent, or the same side of the bounding rectangle). Here, we show that $P$ can be reconfigured to any other simple $s,t$ path of $\mathbb{G}$ by \emph{switching $2\times 2$ squares}, where at most ${5}|\mathbb{G}|/{4}$ such operations are required. Furthermore, each \emph{square-switch} is done in $O(1)$ time and keeps the resulting path in the same family of simple $s,t$ paths. Our reconfiguration result proves that the \emph{Hamiltonian path graph} $\cal{G}$ for simple $s,t$ paths is connected and has diameter at most ${5}|\mathbb{G}|/{4}$ which is asymptotically tight.

preprint2016arXiv

Connecting a Set of Circles with Minimum Sum of Radii

We consider the problem of assigning radii to a given set of points in the plane, such that the resulting set of circles is connected, and the sum of radii is minimized. We show that the problem is polynomially solvable if a connectivity tree is given. If the connectivity tree is unknown, the problem is NP-hard if there are upper bounds on the radii and open otherwise. We give approximation guarantees for a variety of polynomial-time algorithms, describe upper and lower bounds (which are matching in some of the cases), provide polynomial-time approximation schemes, and conclude with experimental results and open problems.

preprint2016arXiv

Connectivity graphs of uncertainty regions

We study connectivity relations among points, where the precise location of each input point lies in a region of uncertainty. We distinguish two fundamental scenarios under which uncertainty arises. In the favorable Best-Case Uncertainty (BU), each input point can be chosen from a given set to yield the best possible objective value. In the unfavorable Worst-Case Uncertainty (WU), the input set has worst possible objective value among all possible point locations, which are uncertain due, for example, to imprecise data. We consider these notions of uncertainty for the bottleneck spanning tree problem, giving rise to the following Best-Case Connectivity with Uncertainty (BCU) problem: Given a family of geometric regions, choose one point per region, such that the longest edge length of an associated geometric spanning tree is minimized. We show that this problem is NP-hard even for very simple scenarios in which the regions are line segments or squares. On the other hand, we give an exact solution for the case in which there are n+k regions, where k of the regions are line segments and n of the regions are fixed points. We then give approximation algorithms for cases where the regions are either all line segments or all unit discs. We also provide approximation methods for the corresponding Worst-Case Connectivity with Uncertainty (WCU) problem: Given a set of uncertainty regions, find the minimal distance r such that for any choice of points, one per region, there is a spanning tree among the points with edge length at most r.

preprint2016arXiv

Monotone Simultaneous Embeddings of Paths in R^d

We study the following problem: Given $k$ paths that share the same vertex set, is there a simultaneous geometric embedding of these paths such that each individual drawing is monotone in some direction? We prove that for any dimension $d \geq 2$ , there is a set of $d+1$ paths that does not admit a monotone simultaneous geometric embedding.

preprint2016arXiv

Visibility Representations of Boxes in 2.5 Dimensions

We initiate the study of 2.5D box visibility representations (2.5D-BR) where vertices are mapped to 3D boxes having the bottom face in the plane $z=0$ and edges are unobstructed lines of sight parallel to the $x$ - or $y$ -axis. We prove that: $(i)$ Every complete bipartite graph admits a 2.5D-BR; $(ii)$ The complete graph $K_n$ admits a 2.5D-BR if and only if $n \leq 19$ ; $(iii)$ Every graph with pathwidth at most $7$ admits a 2.5D-BR, which can be computed in linear time. We then turn our attention to 2.5D grid box representations (2.5D-GBR) which are 2.5D-BRs such that the bottom face of every box is a unit square at integer coordinates. We show that an $n$ -vertex graph that admits a 2.5D-GBR has at most $4n - 6 \sqrt{n}$ edges and this bound is tight. Finally, we prove that deciding whether a given graph $G$ admits a 2.5D-GBR with a given footprint is NP-complete. The footprint of a 2.5D-BR $Γ$ is the set of bottom faces of the boxes in $Γ$ .

preprint2014arXiv

A Simple, Faster Method for Kinetic Proximity Problems

For a set of $n$ points in the plane, this paper presents simple kinetic data structures (KDS's) for solutions to some fundamental proximity problems, namely, the all nearest neighbors problem, the closest pair problem, and the Euclidean minimum spanning tree (EMST) problem. Also, the paper introduces KDS's for maintenance of two well-studied sparse proximity graphs, the Yao graph and the Semi-Yao graph. We use sparse graph representations, the Pie Delaunay graph and the Equilateral Delaunay graph, to provide new solutions for the proximity problems. Then we design KDS's that efficiently maintain these sparse graphs on a set of $n$ moving points, where the trajectory of each point is assumed to be an algebraic function of constant maximum degree $s$ . We use the kinetic Pie Delaunay graph and the kinetic Equilateral Delaunay graph to create KDS's for maintenance of the Yao graph, the Semi-Yao graph, all the nearest neighbors, the closest pair, and the EMST. Our KDS's use $O(n)$ space and $O(n\log n)$ preprocessing time. We provide the first KDS's for maintenance of the Semi-Yao graph and the Yao graph. Our KDS processes $O(n^2β_{2s+2}(n))$ (resp. $O(n^3β_{2s+2}^2(n)\log n)$ ) events to maintain the Semi-Yao graph (resp. the Yao graph); each event can be processed in time $O(\log n)$ in an amortized sense. Here, $β_s(n)$ is an extremely slow-growing function. Our KDS for maintenance of all the nearest neighbors and the closest pair processes $O(n^2β^2_{2s+2}(n)\log n)$ events. For maintenance of the EMST, our KDS processes $O(n^3β_{2s+2}^2(n)\log n)$ events. For all three of these problems, each event can be handled in time $O(\log n)$ in an amortized sense. We improve the previous randomized kinetic algorithm for maintenance of all the nearest neighbors by Agarwal, Kaplan, and Sharir, and the previous EMST KDS by Rahmati and Zarei.

preprint2014arXiv

Kinetic $k$ -Semi-Yao Graph and its Applications

This paper introduces a new proximity graph, called the $k$ -Semi-Yao graph ( $k$ -SYG), on a set $P$ of points in $\mathbb{R}^d$ , which is a supergraph of the $k$ -nearest neighbor graph ( $k$ -NNG) of $P$ . We provide a kinetic data structure (KDS) to maintain the $k$ -SYG on moving points, where the trajectory of each point is a polynomial function whose degree is bounded by some constant. Our technique gives the first KDS for the theta graph (\ie, $1$ -SYG) in $\mathbb{R}^d$ . It generalizes and improves on previous work on maintaining the theta graph in $\mathbb{R}^2$ . As an application, we use the kinetic $k$ -SYG to provide the first KDS for maintenance of all the $k$ -nearest neighbors in $\mathbb{R}^d$ , for any $k\geq 1$ . Previous works considered the $k=1$ case only. Our KDS for all the $1$ -nearest neighbors is deterministic. The best previous KDS for all the $1$ -nearest neighbors in $\mathbb{R}^d$ is randomized. Our structure and analysis are simpler and improve on this work for the $k=1$ case. We also provide a KDS for all the $(1+ε)$ -nearest neighbors, which in fact gives better performance than previous KDS's for maintenance of all the exact $1$ -nearest neighbors. As another application, we present the first KDS for answering reverse $k$ -nearest neighbor queries on moving points in $\mathbb{R}^d$ , for any $k\geq 1$ .

preprint2014arXiv

Kinetic Reverse $k$ -Nearest Neighbor Problem

This paper provides the first solution to the kinetic reverse $k$ -nearest neighbor (\rknn) problem in $\mathbb{R}^d$ , which is defined as follows: Given a set $P$ of $n$ moving points in arbitrary but fixed dimension $d$ , an integer $k$ , and a query point $q\notin P$ at any time $t$ , report all the points $p\in P$ for which $q$ is one of the $k$ -nearest neighbors of $p$ .

preprint2013arXiv

Kinetic Data Structures for the Semi-Yao Graph and All Nearest Neighbors in R^d

This paper presents a simple kinetic data structure for maintaining all the nearest neighbors of a set of $n$ moving points in $\mathbb{R}^d$ , where the trajectory of each point is an algebraic function of at most constant degree $s$ . The approach is based on maintaining the edges of the Semi-Yao graph, a sparse graph whose edge set includes the pairs of nearest neighbors as a subset. Our kinetic data structure (KDS) for maintaining all the nearest neighbors is deterministic. It processes $O(n^2β_{2s+2}^2(n)\log n)$ events with a total cost of $O(n^2β_{2s+2}(n)\log^{d+1} n)$ . Here, $β_s(n)$ is an extremely slow-growing function. The best previous KDS for all the nearest neighbors in $\mathbb{R}^d$ is by Agarwal, Kaplan, and Sharir (TALG 2008). It is a randomized result. Our structure and analysis are simpler than theirs. Also, we improve their result by a factor of $\log^d n$ in the number of events and by a $\log n$ factor in the total cost. This paper generalizes and improves the 2013 work of Rahmati, King and Whitesides (SoCG 2013) on maintaining the Semi-Yao graph in $\mathbb{R}^2$ ; its new technique provides the first KDS for the Semi-Yao graph in $\mathbb{R}^d$ . Our KDS is local in the worst case, meaning that only a constant number of events is associated with any one point at any time. For maintaining all the nearest neighbors, neither our KDS nor the KDS by Agarwal~\etal~is local, and furthermore, each event in our KDS and in their KDS is handled in polylogarithmic time in an amortized sense. Finally, in this paper, we also give a KDS for maintenance of all the $(1+ε)$ -nearest neighbors which is local and each event can be handled in a polylogarithmic worst-case time.

preprint2012arXiv

Computing optimal k-regret minimizing sets with top-k depth contours

Regret minimizing sets are a very recent approach to representing a dataset D with a small subset S of representative tuples. The set S is chosen such that executing any top-1 query on S rather than D is minimally perceptible to any user. To discover an optimal regret minimizing set of a predetermined cardinality is conjectured to be a hard problem. In this paper, we generalize the problem to that of finding an optimal k$regret minimizing set, wherein the difference is computed over top-k queries, rather than top-1 queries. We adapt known geometric ideas of top-k depth contours and the reverse top-k problem. We show that the depth contours themselves offer a means of comparing the optimality of regret minimizing sets using L2 distance. We design an O(cn^2) plane sweep algorithm for two dimensions to compute an optimal regret minimizing set of cardinality c. For higher dimensions, we introduce a greedy algorithm that progresses towards increasingly optimal solutions by exploiting the transitivity of L2 distance.

preprint2012arXiv

Indexing Reverse Top-k Queries

We consider the recently introduced monochromatic reverse top-k queries which ask for, given a new tuple q and a dataset D, all possible top-k queries on D union {q} for which q is in the result. Towards this problem, we focus on designing indexes in two dimensions for repeated (or batch) querying, a novel but practical consideration. We present the insight that by representing the dataset as an arrangement of lines, a critical k-polygon can be identified and used exclusively to respond to reverse top-k queries. We construct an index based on this observation which has guaranteed worst-case query cost that is logarithmic in the size of the k-polygon. We implement our work and compare it to related approaches, demonstrating that our index is fast in practice. Furthermore, we demonstrate through our experiments that a k-polygon is comprised of a small proportion of the original data, so our index structure consumes little disk space.

preprint2003arXiv

The number of transversals to line segments in R^3

We completely describe the structure of the connected components of transversals to a collection of n line segments in R^3. We show that n>2 arbitrary line segments in R^3 admit 0, 1, ..., n or infinitely many line transversals. In the latter case, the transversals form up to n connected components.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Sue Whitesides

Research overview

Is this your work?

12 publications

The Hamiltonian Path Graph is Connected for Simple $s,t$ Paths in Rectangular Grid Graphs

Connecting a Set of Circles with Minimum Sum of Radii

Connectivity graphs of uncertainty regions

Monotone Simultaneous Embeddings of Paths in R^d

Visibility Representations of Boxes in 2.5 Dimensions

A Simple, Faster Method for Kinetic Proximity Problems

Kinetic $k$ -Semi-Yao Graph and its Applications

Kinetic Reverse $k$ -Nearest Neighbor Problem

Kinetic Data Structures for the Semi-Yao Graph and All Nearest Neighbors in R^d

Computing optimal k-regret minimizing sets with top-k depth contours

Indexing Reverse Top-k Queries

The number of transversals to line segments in R^3

See the researcher in context

Building this map preview

Sue Whitesides

Research overview

Is this your work?

12 publications

The Hamiltonian Path Graph is Connected for Simple s,ts,ts,t Paths in Rectangular Grid Graphs

Connecting a Set of Circles with Minimum Sum of Radii

Connectivity graphs of uncertainty regions

Monotone Simultaneous Embeddings of Paths in R^d

Visibility Representations of Boxes in 2.5 Dimensions

A Simple, Faster Method for Kinetic Proximity Problems

Kinetic kkk-Semi-Yao Graph and its Applications

Kinetic Reverse kkk-Nearest Neighbor Problem

Kinetic Data Structures for the Semi-Yao Graph and All Nearest Neighbors in R^d

Computing optimal k-regret minimizing sets with top-k depth contours

Indexing Reverse Top-k Queries

The number of transversals to line segments in R^3

See the researcher in context

Building this map preview

The Hamiltonian Path Graph is Connected for Simple $s,t$ Paths in Rectangular Grid Graphs

Kinetic $k$ -Semi-Yao Graph and its Applications

Kinetic Reverse $k$ -Nearest Neighbor Problem