Source author record

Paul Seiferth

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

Catalog footprint

Research overview

3works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2019arXiv

Reachability Oracles for Directed Transmission Graphs

Let $P \subset \mathbb{R}^d$ be a set of $n$ points in $d$ dimensions such that each point $p \in P$ has an associated radius $r_p > 0$ . The transmission graph $G$ for $P$ is the directed graph with vertex set $P$ such that there is an edge from $p$ to $q$ if and only if $|pq| \leq r_p$ , for any $p, q \in P$ . A reachability oracle is a data structure that decides for any two vertices $p, q \in G$ whether $G$ has a path from $p$ to $q$ . The quality of the oracle is measured by the space requirement $S(n)$ , the query time $Q(n)$ , and the preprocessing time. For transmission graphs of one-dimensional point sets, we can construct in $O(n \log n)$ time an oracle with $Q(n) = O(1)$ and $S(n) = O(n)$ . For planar point sets, the ratio $Ψ$ between the largest and the smallest associated radius turns out to be an important parameter. We present three data structures whose quality depends on $Ψ$ : the first works only for $Ψ< \sqrt{3}$ and achieves $Q(n) = O(1)$ with $S(n) = O(n)$ and preprocessing time $O(n\log n)$ ; the second data structure gives $Q(n) = O(Ψ^3 \sqrt{n})$ and $S(n) = O(Ψ^3 n^{3/2})$ ; the third data structure is randomized with $Q(n) = O(n^{2/3}\log^{1/3} Ψ\log^{2/3} n)$ and $S(n) = O(n^{5/3}\log^{1/3} Ψ\log^{2/3} n)$ and answers queries correctly with high probability.

preprint2014arXiv

Approximate k-flat Nearest Neighbor Search

Let $k$ be a nonnegative integer. In the approximate $k$ -flat nearest neighbor ( $k$ -ANN) problem, we are given a set $P \subset \mathbb{R}^d$ of $n$ points in $d$ -dimensional space and a fixed approximation factor $c > 1$ . Our goal is to preprocess $P$ so that we can efficiently answer approximate $k$ -flat nearest neighbor queries: given a $k$ -flat $F$ , find a point in $P$ whose distance to $F$ is within a factor $c$ of the distance between $F$ and the closest point in $P$ . The case $k = 0$ corresponds to the well-studied approximate nearest neighbor problem, for which a plethora of results are known, both in low and high dimensions. The case $k = 1$ is called approximate line nearest neighbor. In this case, we are aware of only one provably efficient data structure, due to Andoni, Indyk, Krauthgamer, and Nguyen. For $k \geq 2$ , we know of no previous results. We present the first efficient data structure that can handle approximate nearest neighbor queries for arbitrary $k$ . We use a data structure for $0$ -ANN-queries as a black box, and the performance depends on the parameters of the $0$ -ANN solution: suppose we have an $0$ -ANN structure with query time $O(n^ρ)$ and space requirement $O(n^{1+σ})$ , for $ρ, σ> 0$ . Then we can answer $k$ -ANN queries in time $O(n^{k/(k + 1 - ρ) + t})$ and space $O(n^{1+σk/(k + 1 - ρ)} + n\log^{O(1/t)} n)$ . Here, $t > 0$ is an arbitrary constant and the $O$ -notation hides exponential factors in $k$ , $1/t$ , and $c$ and polynomials in $d$ . Our new data structures also give an improvement in the space requirement over the previous result for $1$ -ANN: we can achieve near-linear space and sublinear query time, a further step towards practical applications where space constitutes the bottleneck.

preprint2013arXiv

Greedy is as Good as Delaunay (Almost)

Let S be a planar point set. Krznaric and Levcopoulos proved that given the Delaunay triangulation DT(S) for S, one can find the greedy triangulation GT(S) in linear time. We provide a (partial) converse of this result: given GT(S), it is possible to compute DT(S) in linear expected time. Thus, these structures are basically equivalent. To obtain our result, we generalize another algorithm by Krznaric and Levcopoulos to find a hierarchical clustering for S in linear time, once DT(S) is known. We show that their algorithm remains (almost) correct for any triangulation of bounded dilation, i.e., any triangulation in which the shortest path distance between any two points approximates their Euclidean distance. In general, however, the resulting running time may be superlinear. Nonetheless, we can show that the properties of the greedy triangulation suffice to guarantee a linear time bound.

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.