Given a set S of n points in the plane, we study the two-line-center problem: finding two lines that minimize the maximum distance from each point in S to its closest line. We present a (1+ε)-approximation algorithm for the two-line-center problem that runs in O((n/ε) log (1/ε)) time, which improves the previously best O(nlog n + (n/ε²) log (1/ε) + (1/ε³)log (1/ε))-time algorithm. We also consider three variants of this problem, in which the orientations of the two lines are restricted: (1) the orientation of one of the two lines is fixed, (2) the orientations of both lines are fixed, and (3) the two lines are required to be parallel. For each of these three variants, we give the first (1+ε)-approximation algorithm that runs in linear time. In particular, for the variant where the orientation of one of the two lines is fixed, we also give an improved exact algorithm that runs in O(n log n) time and show that it is optimal.

Oriented spanners were presented at ESA'23 as an extension of the well-researched geometric spanners: Given a set P of points in a metric space and an oriented graph G, the oriented dilation of two points p,q ∈ P is the length of the shortest closed walk in G containing p and q divided by the minimum perimeter triangle of p and q. G is called a t-spanner, if the maximum dilation over all pairs of points in P is at most t. This paper presents the first constructions of sparse oriented spanners for metric spaces beyond the Euclidean space. Given an orientation of the complete graph (i.e. a tournament) with dilation t on n points that satisfies an additional short-cycle property, we show how to extract a (t+ε)-spanner with 𝒪(k) edges in 𝒪(kn²+T(n)) time, for any metric space admitting a well-separated pair decomposition with k pairs computable in T(n) time. We supplement this with an improved construction of tournaments for metric point sets, obtaining dilation 5/3. This improves the previous bound of 2 and approaches the lower bound of 1.5. Combined, for n points in a metric space with constant doubling dimension d, this yields a (5/3 + ε)-spanner with (1/ε)^{𝒪(d)}n edges computable in (1/ε)^𝒪(d) n³ time using 𝒪(n²) space. This improves the dilation over the (2+ε)-spanner for Euclidean point sets presented at SoCG’25 while applying to more general metric spaces. Moreover, we generalize the known (2+ε)-spanner to doubling spaces. In particular, an oriented (2+ε)-spanner with 𝒪(ε^{-d} n) edges can be constructed in (1/ε)^𝒪(d) n log n time using 𝒪(ε^{-d} n) space. Since the oriented dilation can be dominated by one pair of points, we also consider the oriented average dilation, which is the sum over the oriented dilation of all pairs of points divided by the number of pairs. While oriented (1+ε)-spanners do not exist for every point set, we present an algorithm that computes a spanner with average dilation 1+ε for point sets in a metric space of constant doubling dimension d: More concretely, our algorithm computes an oriented spanner with average dilation at most 1 + 𝒪(1/s) + s^𝒪(d)/n with s^𝒪(d) n edges in s^𝒪(d) n log n time using s^𝒪(d) n space, where s is any sufficiently large number that may depend on n.

A hypergraph $H$ consists of a set $V$ of vertices and a set $E$ of hyperedges that are subsets of $V$. A $t$-tuple of $H$ is a subset of $t$ vertices of $V$. A $t$-tuple $k$-coloring of $H$ is a mapping of its $t$-tuples into $k$ colors. A coloring is called $(t,k,f)$-polychromatic if each hyperedge of $E$ that has at least $f$ vertices contains tuples of all the $k$ colors. Let $f_H(t,k)$ be the minimum $f$ such that $H$ has a $(t,k,f)$-polychromatic coloring. For a family of hypergraphs $\cal{H}$ let $f_{\cal{H}}(t,k)$ be the maximum $f_H(t,k)$ over all hypergraphs $H$ in $\cal{H}$. We present several bounds on $f_{\cal{H}}(t,k)$ for $t\ge 2$. - Let $\cal{H}$ be the family of hypergraphs $H$ that is obtained by taking any set $P$ of points in $\Re^2$, setting $V:=P$ and $E:=\{d\cap P\colon d\text{ is a disk in }\Re^2\}$. We prove that $f_\cal{H}(2,k)\le 3.7^k$, that is, the pairs of points (2-tuples) can be $k$-colored such that any disk containing at least $3.7^k$ points has pairs of all colors. - For the family $\mathcal{H}$ of shrinkable hypergraphs of VC-dimension at most $d$ we prove that $ f_\cal{H}(d{+}1,k) \leq c^k$ for some constant $c=c(d)$. We also prove that every hypergraph with $n$ vertices and with VC-dimension at most $d$ has a $(d{+}1)$-tuple $T$ of depth at least $\frac{n}{c}$, i.e., any hyperedge that contains $T$ also contains $\frac{n}{c}$ other vertices. - For the relationship between $t$-tuple coloring and vertex coloring in any hypergraph $H$ we establish the inequality $\frac{1}{e}\cdot tk^{\frac{1}{t}}\le f_H(t,k)\le f_H(1,tk^{\frac{1}{t}})$. For the special case of $k=2$, we prove that $t+1\le f_H(t,2)\le\max\{f_H(1,2), t+1\}$; this improves upon the previous best known upper bound. - We generalize some of our results to higher dimensions, other shapes, pseudo-disks, and also study the relationship between tuple coloring and epsilon nets.

Given a point set P in a metric space and a real number t ≥ 1, an oriented t-spanner is an oriented graph G = (P, E), where for every pair of distinct points p and q in P, the shortest oriented closed walk in G that contains p and q is at most a factor t longer than the perimeter of the smallest triangle in P containing p and q. The oriented dilation of a graph G is the minimum t for which G is an oriented t-spanner. For arbitrary point sets of size n in ℝ^d, where d ≥ 2 is a constant, the only known oriented spanner construction is an oriented 2-spanner with binom(n,2) edges. Moreover, there exists a set P of four points in the plane, for which the oriented dilation is larger than 1.46, for any oriented graph on P. We present the first algorithm that computes, in Euclidean space, a sparse oriented spanner whose oriented dilation is bounded by a constant. More specifically, for any set of n points in ℝ^d, where d is a constant, we construct an oriented (2+ε)-spanner with 𝒪(n) edges in 𝒪(n log n) time and 𝒪(n) space. Our construction uses the well-separated pair decomposition and an algorithm that computes a (1+ε)-approximation of the minimum-perimeter triangle in P containing two given query points in 𝒪(log n) time. While our algorithm is based on first computing a suitable undirected graph and then orienting it, we show that, in general, computing the orientation of an undirected graph that minimises its oriented dilation is NP-hard, even for point sets in the Euclidean plane. We further prove that even if the oriented graph is already given, computing its oriented dilation is APSP-hard for points in a general metric space. We complement this result with an algorithm that approximates the oriented dilation of a given graph in subcubic time for point sets in ℝ^d, where d is a constant.

A covering path for a finite set P of points in the plane is a polygonal path such that every point of P lies on a segment of the path. The vertices of the path need not be at points of P. A covering path is plane if its segments do not cross each other. Let π(n) be the minimum number such that every set of n points in the plane admits a plane covering path with at most π(n) segments. We prove that π(n) ≤ ⌈6n/7⌉. This improves the previous best-known upper bound of ⌈21n/22⌉, due to Biniaz (SoCG 2023). Our proof is constructive and yields a simple O(n log n)-time algorithm for computing a plane covering path.

Let S be a set of n points in ℝ^d, where d ≥ 2 is a constant, and let H₁,H₂,…,H_{m+1} be a sequence of vertical hyperplanes that are sorted by their first coordinates, such that exactly n/m points of S are between any two successive hyperplanes. Let |A(S,m)| be the number of different closest pairs in the {(m+1) choose 2} vertical slabs that are bounded by H_i and H_j, over all 1 ≤ i < j ≤ m+1. We prove tight bounds for the largest possible value of |A(S,m)|, over all point sets of size n, and for all values of 1 ≤ m ≤ n. As a result of these bounds, we obtain, for any constant ε > 0, a data structure of size O(n), such that for any vertical query slab Q, the closest pair in the set Q ∩ S can be reported in O(n^{1/2+ε}) time. Prior to this work, no linear space data structure with sublinear query time was known.

A beer graph is an undirected graph G, in which each edge has a positive weight and some vertices have a beer store. A beer path between two vertices u and v in G is any path in G between u and v that visits at least one beer store. We show that any outerplanar beer graph G with n vertices can be preprocessed in O(n) time into a data structure of size O(n), such that for any two query vertices u and v, (i) the weight of the shortest beer path between u and v can be reported in $$O(\alpha (n))$$ time (where $$\alpha (n)$$ is the inverse Ackermann function), and (ii) the shortest beer path between u and v can be reported in O(L) time, where L is the number of vertices on this path. Note that the running time for (ii) does not depend on the number of vertices of G. Both results are optimal, even when G is a beer tree (i.e., a beer graph whose underlying graph is a tree).

Given two sets $S$ and $T$ of points in the plane, of total size $n$, a {many-to-many} matching between $S$ and $T$ is a set of pairs $(p,q)$ such that $p\in S$, $q\in T$ and for each $r\in S\cup T$, $r$ appears in at least one such pair. The {cost of a pair} $(p,q)$ is the (Euclidean) distance between $p$ and $q$. In the {minimum-cost many-to-many matching} problem, the goal is to compute a many-to-many matching such that the sum of the costs of the pairs is minimized. This problem is a restricted version of minimum-weight edge cover in a bipartite graph, and hence can be solved in $O(n^3)$ time. In a more restricted setting where all the points are on a line, the problem can be solved in $O(n\log n)$ time [Colannino, Damian, Hurtado, Langerman, Meijer, Ramaswami, Souvaine, Toussaint; Graphs Comb., 2007]. However, no progress has been made in the general planar case in improving the cubic time bound. In this paper, we obtain an $O(n^2\cdot poly(\log n))$ time exact algorithm and an $O( n^{3/2}\cdot poly(\log n))$ time $(1+ε)$-approximation in the planar case. Our results affirmatively address an open problem posed in [Colannino et al., Graphs Comb., 2007].

We present a routing algorithm for the Θ4-graph that computes a path between any two vertices s and t having length at most 17 times the Euclidean distance between s and t. To compute this path, at each step, the algorithm only uses knowledge of the location of the current vertex, its (at most four) outgoing edges, the destination vertex, and one additional bit of information in order to determine the next edge to follow. This provides the first known online, local, competitive routing algorithm with constant routing ratio for the Θ4-graph, as well as improving the best known upper bound on the spanning ratio of these graphs from 237 to 17. We also show that without this additional bit of information, the routing ratio increases to ≈ 17.03.

We consider a well studied generalization of the maximum clique problem which is defined as follows. Given a graph G on n vertices and an integer d >= 1, in the maximum diameter-bounded subgraph problem (MaxDBS for short), the goal is to find a (vertex) maximum subgraph of G of diameter at most d. For d=1, this problem is equivalent to the maximum clique problem and thus it is NP-hard to approximate it within a factor n^{1-epsilon}, for any epsilon > 0. Moreover, it is known that, for any d >= 2, it is NP-hard to approximate MaxDBS within a factor n^{1/2 - epsilon}, for any epsilon > 0. In this paper we focus on MaxDBS for the class of unit disk graphs. We provide a polynomial-time constant-factor approximation algorithm for the problem. The approximation ratio of our algorithm does not depend on the diameter d. Even though the algorithm itself is simple, its analysis is rather involved. We combine tools from the theory of hypergraphs with bounded VC-dimension, k-quasi planar graphs, fractional Helly theorems and several geometric properties of unit disk graphs.

A geometric graph G=(P,E) is a set of points in the plane and edges between pairs of points, where the weight of an edge is equal to the Euclidean distance between its two endpoints. In local routing we find a path through G from a source vertex s to a destination vertex t, using only knowledge of the current vertex, its incident edges, and the locations of s and t. We present an algorithm for local routing on the Delaunay triangulation, and show that it finds a path between a source vertex s and a target vertex t that is not longer than 3.56|st|, improving the previous bound of 5.9|st|.

Let S be a finite set of points in the plane that are in convex position. We present an algorithm that constructs a plane frac{3+4 pi}{3}-spanner of S whose vertex degree is at most 3. Let Lambda be the vertex set of a finite non-uniform rectangular lattice in the plane. We present an algorithm that constructs a plane 3 sqrt{2}-spanner for Lambda whose vertex degree is at most 3. For points that are in the plane and in general position, we show how to compute plane degree-3 spanners with a linear number of Steiner points.

Highly connected and yet sparse graphs (such as expanders or graphs of high treewidth) are fundamental, widely a pplicable and extensively studied combinatorial objects. We initiate the study of such highly connected graphs that are, in addition, geometric spanners. We define a property of spanners called robustness. Informally, when one removes a few vertices from a robust spanner, this harms only a small number of other vertices. We show that robust spanners must have a superlinear number of edges, even in one dimension. On the positive side, we give constructions, for any dimension, of robust spanners with a near-linear number of edges.

Highly connected and yet sparse graphs (such as expanders or graphs of high treewidth) are fundamental, widely applicable, and extensively studied combinatorial objects. We initiate the study of such highly connected graphs that are, in addition, geometric spanners. We define a property of spanners called robustness. Informally, when one removes a few vertices from a robust spanner, this harms only a small number of other vertices. We show that robust spanners must have a superlinear number of edges, even in one dimension. On the positive side, we give constructions, for any dimension, of robust spanners with a near-linear number of edges.

Let (S,d) be a finite metric space, where each element p∈S has a non-negative weight w (p). We study spanners for the set S with respect to the following weighted distance function: $$\mathbf{d}_{\omega}(p,q)=\left\{\begin{array}{ll}0&\mbox{ if $p=q$,}\\ \operatorname {w}(p)+\mathbf{d}(p,q)+ \operatorname {w}(q)&\mbox{ if $p\neq q$.}\end{array}\right.$$ We present a general method for turning spanners with respect to the d-metric into spanners with respect to the d ω -metric. For any given ε>0, we can apply our method to obtain (5+ε)-spanners with a linear number of edges for three cases: points in Euclidean space ℝ d , points in spaces of bounded doubling dimension, and points on the boundary of a convex body in ℝ d where d is the geodesic distance function. We also describe an alternative method that leads to (2+ε)-spanners for weighted point points in ℝ d and for points on the boundary of a convex body in ℝ d . The number of edges in these spanners is O(nlog n). This bound on the stretch factor is nearly optimal: in any finite metric space and for any ε>0, it is possible to assign weights to the elements such that any non-complete graph has stretch factor larger than 2−ε.

We address the following problem: Given a complete k-partite geometric graph K whose vertex set is a set of n points in $\mathbb{R}^d$, compute a spanner of K that has a “small” stretch factor and “few” edges. We present two algorithms for this problem. The first algorithm computes a $(5+\epsilon)$-spanner of K with $O(n)$ edges in $O(n\log n)$ time. The second algorithm computes a $(3+\epsilon)$-spanner of K with $O(n\log n)$ edges in $O(n \log n)$ time. The latter result is optimal: We show that for any $2\leq k\leq n-\Theta(\sqrt{n\log n})$, spanners with $O(n\log n)$ edges and stretch factor less than 3 do not exist for all complete k-partite geometric graphs.

Given an arbitrary real constant ε > 0, and a geometric graph G in d -dimensional Euclidean space with n points, O ( n ) edges, and constant dilation, our main result is a data structure that answers (1 + ε)-approximate shortest-path-length queries in constant time. The data structure can be constructed in O ( n log n ) time using O ( n log n ) space. This represents the first data structure that answers (1 + ε)-approximate shortest-path queries in constant time, and hence functions as an approximate distance oracle. The data structure is also applied to several other problems. In particular, we also show that approximate shortest-path queries between vertices in a planar polygonal domain with “rounded” obstacles can be answered in constant time. Other applications include query versions of closest-pair problems, and the efficient computation of the approximate dilations of geometric graphs. Finally, we show how to extend the main result to answer (1 + ε)-approximate shortest-path-length queries in constant time for geometric spanner graphs with m = ω( n ) edges. The resulting data structure can be constructed in O ( m + n log n ) time using O ( n log n ) space.

This paper proposes using collisions of Pareto random variables in traffic analysis and in generating fictitious network traffic that follows various Pareto distributions. Pareto distributions are commonly found in network statistics, but the distributions may be truncated or overlapping, thus making it hard to estimate their sample parameters. Therefore, this paper investigates methods of computing parameters of binned collisions of Pareto random variables. This paper explores an indicator variable approach to analyzing collisions of Pareto random variables. These collisions are initially modeled by the birthday problem or paradox and then they are extended to understand independence of collisions. This paper's use of indicator variables simplifies the calculation of higher moments for binned collisions of Pareto random variables

There are several results available in the literature dealing with efficient construction of t-spanners for a given set S of n points in $\IR^d$. t-spanners are Euclidean graphs in which distances between vertices in G are at most t times the Euclidean distances between them; in other words, distances in G are "stretched" by a factor of at most t. We consider the interesting dual problem: given a Euclidean graph G whose vertex set corresponds to the set S, compute the stretch factor of G, i.e., the maximum ratio between distances in G and the corresponding Euclidean distances. It can trivially be solved by solving the all-pairs-shortest-path problem. However, if an approximation to the stretch factor is sufficient, then we show it can be efficiently computed by making only O(n) approximate shortest path queries in the graph G. We apply this surprising result to obtain efficient algorithms for approximating the stretch factor of Euclidean graphs such as paths, cycles, trees, planar graphs, and general graphs. The main idea behind the algorithm is to use Callahan and Kosaraju's well-separated pair decomposition.

In Layered Manufacturing, the choice of the build direction for the model inuences several design criteria, including the number of layers, the volume and contact-area of the support structures, and the surface nish. These, in turn, impact the throughput and cost of the process. In this paper, ecient geometric algorithms are given to reconcile two or more of these criteria simultaneously, under three formulations of multi-criteria optimization: Finding a build direction which (i) optimizes the criteria sequentially, (ii) optimizes their weighted sum, or (iii) allows the criteria to meet designer-prescribed thresholds. The algorithms that involve \\support volume" or \\contact area" apply only to convex models, while the algorithms that involve \\surface nish" and \\number of layers" apply to any polyhedral model. Some of the latter algorithms have also been implemented and tested on real-world models obtained from industry. The geometric techniques used in the paper include construction and searching of certain arrangements on the unit-sphere, three-dimensional convex hulls, Voronoi diagrams, point location, and hierarchical representations. Additionally, solutions are also provided, for the constrained versions of two geometric problems, namely polyhedron width and largest empty disk on the unit-sphere. 1

Let S be a set of n points in lKd, and k m integer such that 1 5 k 5 n -2.Algorithms are given that construct fault-tolerant spanners for S. If in such a spanner at most k edges or vertices are removed, then each pair of points in the remaining graph is still connected by a short path.Our results include (i) an algorithm with running time O(n logdB1 n + kn log log n + k2n) that constructs a spanner with O(k2n) edges, that is resilient to k edge faults, (ii) an algorithm with running time O(n logn + k2n) that constructs a spanner with O(k2n) edges, that is resilient to k vertex faults, and (iii) an algorithm with rllnning time O(n logn+&n) that constructs a spanner of degree O(s), whose total edge length is bounded by G(2) times the weight of a miuimum spanning tree of S, and that is resilient to k edge or vertex faults.Here, c is a constant that is independent of n and Ic.

We describe a new randomized data structure, the sparse partition, for solving the dynamic closest-pair problem. Using this data structure the closest pair of a set of n points in D-dimensional space, for any fixed D, can be found in constant time. If a frame containing all the points is known in advance, and if the floor function is available at unit cost, then the data structure supports insertions into and deletions from the set in expected O(log n) time and requires expected O(n) space. This method is more efficient than any deterministic algorithm for solving the problem in dimension D > 1. The data structure can be modified to run in O(log 2 n) expected time per update in the algebraic computation tree model. Even this version is more efficient than the best currently known deterministic algorithm for D > 2. Both results assume that the sequence of updates is not determined in any way by the random choices made by the algorithm.

Article Computing the minimum diameter for moving points: an exact implementation using parametric search Share on Authors: Jörg Schwerdt Fakultät für Informatik, Otto-von-Guericke-Universität, Magdeburg, Universitätsplatz 2, D-39106 Magdeburg, Germany Fakultät für Informatik, Otto-von-Guericke-Universität, Magdeburg, Universitätsplatz 2, D-39106 Magdeburg, GermanyView Profile , Michiel Smid Fakultät für Informatik, Otto-von-Guericke-Universität, Magdeburg, Universitätsplatz 2, D-39106 Magdeburg, Germany Fakultät für Informatik, Otto-von-Guericke-Universität, Magdeburg, Universitätsplatz 2, D-39106 Magdeburg, GermanyView Profile , Stefan Schirra Max-Planck-Institut für Informatik, Im Stadtwald, D-66123 Saarbrücken, Germany Max-Planck-Institut für Informatik, Im Stadtwald, D-66123 Saarbrücken, GermanyView Profile Authors Info & Claims SCG '97: Proceedings of the thirteenth annual symposium on Computational geometryAugust 1997 Pages 466–468https://doi.org/10.1145/262839.263087Online:01 August 1997Publication History 6citation275DownloadsMetricsTotal Citations6Total Downloads275Last 12 Months2Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Let S be a set of n points in $\mathbb{R}^D $. It is shown that a range tree can be used to find an $L_\infty $-nearest neighbor in S of any query point in $O((\log n)^{D - 1} \log \log n)$ time. This data structure has size $O(n(\log n)^{D - 1} )$ and an amortized update time of $O((\log n)^{D - 1} \log \log n)$. This result is used to solve the $(1 + \epsilon )$-approximate $L_2 $-nearest-neighbor problem within the same bounds (up to a constant factor that depends on $\epsilon $ and D). In this problem, for any query point p, a point $q \in S$ is computed such that the euclidean distance between p and q is at most $(1 + \epsilon )$ times the euclidean distance between p and its true nearest neighbor. This is the first dynamic data structure for this problem having close to linear size and polylogarithmic query and update times. New dynamic data structures are given that maintain a closest pair of S. For $D \geqslant 3$, a structure of size $O(n)$ is presented with amortized update time $O((\log n)^{D - 1} \log \log n)$. The constant factor in this space (resp. time bound) is of the form $O(D)^D $ (res. $2^{O(D^2 )} $. For $D = 2$ and any nonnegative integer constant k, structures of size $O({{n\log n} / {(\log \log n)^k}} )$ (resp. $O(n)$) are presented that have an amortized update time of $O(\log n\log \log n)$ (resp. $O({{(\log n)^2 } / {(\log \log n)^k}} )$). Previously, no deterministic linear size data structure having polylogarithmic update time was known for this problem.

Euclidean spanners are important data structures in geometric algorithm design, because they provide a means of approximating the complete Euclidean graph with only O(n) edges, so that the shortest path length between each pair of points is not more than a constant factor longer than the Euclidean distance between the points. In many applications of spanners, it is important that the spanner possess a number of additional properties: low tot al edge weight, bounded degree, and low diameter. Existing research on spanners has considered one property or the other. We show that it is possible to build spanners in optimal O (n log n) time and O(n) space that achieve optimal or near optimal tradeoffs between all combinations of these *Max-Planck-Institut fiir Informatik, D-66123 Saarbrucken, Germany. Email: {arya, michiel}@mpi-sb. mpg. de. Supported by the ESPRIT Basic Research Actions Program, under contract No. 7141 (project ALCOM 11). t Math Sciences Dept., The University of Memphis, Memphis, TN 38152. Supported in part by NSF Grant CCR9306822. E-mail: dasg@next 1.msci .memst . edu. i Department of Computer Science and Institute for Advanced Computer Studies, University of Maryland, College Park, Maryland. Partially supported by NSF Grant CCR-93107O5. This work was done while visiting the Max-Planck-Institut fiir Informatik, Saarbriicken. E-mail: mount @cs. umd. edu. SQue~Tech, IIIC., 7600A Leesburg Pike, Falls Church, VA 22043. This work was done while visiting the Max-Planck-Institut fiir Informatik, Saarbriicken. E-mail: jsalowet!nvl, army .mil. Permission to copy without fee all or part of thk material is granted provided that the copies are not made or distributed for direct commercial advantage, the ACM copyri ht notice and the title of thq publication and, is date appear, a#notice is given that copyt~isby~n,sslon of the Ass@ationof Computing Machinery. o cop otherwise, or to republish, requires a fee ancf/or speci ic permission. STOC’ 95, Las Vegas, Nevada, USA @ 1995 ACM 0-89791 -718-9/95/0005..$3.50 properties. We achieve these results in large part because of a new structure, called the dumbbell tree which provides a method of decomposing a spanner into a constant number of trees, so that each of the O(n2) spanner paths is mapped entirely to a path in one of these trees.

Generalized intersection searching problems are a class of geometric query-retrieval problems where the questions of interest concern the intersection of a query object with aggregates of geometric objects (rather than with individual objects.) This class contains, as a special case, the well-studied class of standard intersection searching problems and is rich in applications. Unfortunately, the solutions known for the standard problems do not yield efficient solutions to the generalized problems. Recently, efficient solutions have been given for generalized problems where the input and query objects are iso-oriented (i.e., axes-parallel) or where the aggregates satisfy additional properties (e.g., connectedness). In this paper, efficient algorithms are given for several generalized problems involving non-iso-oriented objects. These problems include: generalized halfspace range searching, segment intersection searching, triangle stabbing, and triangle range searching. The techniques used include: computing suitable sparse representations of the input, persistent data structures, and filtering search.

Let S be a set of n points in RD. It is shown that a range tree can be used to find an L∞ -nearest neighbor in S of any query point, in O((logn)D-1 loglogn) time. This data structure has size O(n(logn)D-1) and an amortized update time of O((logn)D-1 loglogn). This result is used to solve the (1+ ϵ)-approximate L2-nearest neighbor problem within the same bounds. In this problem, for any query point p, a point ∈ is computed such that the euclidean distance between p and q is at most (1+ϵ) times the euclidean distance between p and its true nearest neighbor. This is the first dynamic data structure for this problem having close to linear size and polylogarithmic query and update times.

Let S be a set of n points in IR/sup d/ and let t>1 be a real number. A t-spanner for S is a directed graph having the points of S as its vertices, such that for any pair p and q of points there is a path from p to q of length at most t times the Euclidean distance between p and p. Such a path is called a t-spanner path. The spanner diameter of such a spanner is defined as the smallest integer D such that for any pair p and q of points there is a t-spanner path from p to q containing at most D edges. Randomized and deterministic algorithms are given for constructing t-spanners consisting of O(n) edges and having O(log n) diameter. Also, it is shown how to maintain the randomized t-spanner under random insertions and deletions. Previously, no results were known for spanners with low spanner diameter and for maintaining spanners under insertions and deletions.>

We give an algorithm that computes the closest pair in a set of n points in k- dimensional space on-line, in O(n log n) time. The algorithm only uses algebraic functions and, therefore, is optimal. The algorithm maintains a hierarchical subdivision of k-space into hyperrectangles, which is stored in a binary tree. Centroids are used to maintain a balanced decomposition of this tree. 1 Introduction The closest pair problem is one of the classical problems in computational geometry. In this problem, we have to compute the closest pair---or its distance---in a set of n points in k-dimensional space. Distances are measured in an arbitrary, but fixed, L t -metric. Let p = (p 1 ; : : : ; p k ) and q = (q 1 ; : : : ; q k ) be two points in k-dimensional space. Then the L t -distance d t (p; q) between p and q is defined by d t (p; q) := / k X i=1 jp i \\Gamma q i j t !1=t ; if 1 t ! 1, and for t = 1, it is defined by d1 (p; q) := max 1ik jp i \\Gamma q i j: We observe, as many o...

Let S be a set of n points in D-dimensional space, where D is a constant, and let k be an integer between 1 and (/sub 2//sup n/) An algorithm is given that computes the k closest pairs in the set S in O(nlogn+k) time, using O(n+k) space. The algorithm fits in the algebraic decision tree model and is, therefore, optimal.>