We propose an algorithm for the problem of computing shortest paths among curved obstacles in the plane. If the obstacles have $O(n)$ description complexity, then the algorithm runs in $O(n\log n)$ time plus a term dependent on the properties of the boundary arcs. Specifically, if the arcs allow a certain kind of bisector intersection to be computed in constant time, or even in $O(\log n)$ time, then the running time of the overall algorithm is $O(n \log n)$. If the arcs support only constant-time tangent, intersection, and length queries, as is customarily assumed, then the algorithm computes an approximate shortest path, with relative error $\varepsilon$, in time $O(n\log n + n\log \frac{1}{\varepsilon})$. In fact, the algorithm computes an approximate shortest path map, a data structure with $O(n\log n)$ size, that allows it to report the (approximate) length of a shortest path from a fixed source point to any query point in the plane in $O(\log n)$ time. By applying an idea due to Wang [ Proceedings of the $32$nd Annual ACM-SIAM Symposium on Discrete Algorithms, 2021, pp. 810--821], the algorithm's working storage and the size of the approximate shortest path map can be reduced to $O(n)$.

We study the problem of finding shortest paths in the plane among h convex obstacles, where the path is allowed to pass through (violate) up to k obstacles, for $$k \le h$$ . Equivalently, the problem is to find shortest paths that become obstacle-free if k obstacles are removed from the input. Given a fixed source point s, we show how to construct a map, called a shortest k-path map, so that all destinations in the same region of the map have the same combinatorial shortest path passing through at most k obstacles. We prove a tight bound of $$\varTheta (kn)$$ on the size of this map, and show that it can be computed in $$O(k^2n \log n)$$ time, where n is the total number of obstacle vertices.

We describe an O(n^d) time algorithm for computing the exact probability that two d-dimensional probabilistic point sets are linearly separable, for any fixed d >= 2. A probabilistic point in d-space is the usual point, but with an associated (independent) probability of existence. We also show that the d-dimensional separability problem is equivalent to a (d+1)-dimensional convex hull membership problem, which asks for the probability that a query point lies inside the convex hull of n probabilistic points. Using this reduction, we improve the current best bound for the convex hull membership by a factor of n [Agarwal et al., ESA, 2014]. In addition, our algorithms can handle "input degeneracies" in which more than k+1 points may lie on a k-dimensional subspace, thus resolving an open problem in [Agarwal et al., ESA, 2014]. Finally, we prove lower bounds for the separability problem via a reduction from the k-SUM problem, which shows in particular that our O(n^2) algorithms for 2-dimensional separability and 3-dimensional convex hull membership are nearly optimal.

We consider the problem of computing k shortest paths in a two-dimensional environment with polygonal obstacles, where the jth path, for 1 ≤ j ≤ k, is the shortest path in the free space that is also homotopically distinct from each of the first j – 1 paths. In fact, we consider a more general problem: given a source point s, construct a partition of the free space, called the kth shortest path map (k-SPM), in which the homotopy of the kth shortest path in a region has the same structure. Our main combinatorial result establishes a tight bound of Θ(k2h + kn) on the worst-case complexity of this map. We also describe an O((k3h + k2n) log (kn)) time algorithm for constructing the map. In fact, the algorithm constructs the jth map for every j ≤ k. Finally, we present a simple visibility-based algorithm for computing the k shortest paths between two fixed points. This algorithm runs in O(m log n + k) time and uses O(m + k) space, where m is the size of the visibility graph. This latter algorithm can be extended to compute k shortest simple (non-self-intersecting) paths, taking O(k2 m(m + kn) log (kn)) time. We invite the reader to play with our applet demonstrating k-SPMs [10].

No abstract available.

We propose an algorithm for the problem of computing shortest paths among curved obstacles in the plane. If the obstacles have O(n) description complexity, then the algorithm runs in O(n log n) time plus a term dependent on the properties of the boundary arcs. Specifically, if the arcs allow a certain kind of bisector intersection to be computed in constant time, or even in O(log n) time, then the running time of the overall algorithm is O(n log n). If the arcs support only constant-time tangent, intersection, and length queries, as is customarily assumed, then the algorithm computes an approximate shortest path, with relative error ε, in time O(n log n + n log 1/ε). In fact, the algorithm computes an approximate shortest path map, a data structure with O(n log n) size, that allows it to report the (approximate) length of a shortest path from a fixed source point to any query point in the plane in O(log n) time.

Multiple objects in the plane are called pseudodisks if the boundaries of any two of them intersect transversely at most twice. Given a set of $n$ (possibly intersecting) convex pseudodisks of $O(1)$ complexity each and two points $s$ and $t$ in the plane, we present an efficient algorithm for computing a shortest $s$-to-$t$ path avoiding the pseudodisks. After the union of the pseudodisks is computed, which can be done in $O(n\log n)$ randomized time or $O(n\log^2 n)$ deterministic time, our algorithm runs in $O(n\log n+k)$ deterministic time, where $k$ is the size of the extended visibility graph of the union of the pseudodisks. Note that $k = O(n^2)$ in the worst case. In over two decades, the previously best algorithms for this problem have not improved on the bound of $O(n^2\log n)$ time, even when all the pseudodisks are pairwise disjoint disks. Our technique is also applicable to a motion planning problem of finding a shortest path to translate a convex object in the plane from one location to another avoiding a given set of polygonal obstacles, improving the previously best known solution and settling an open problem posed in 1988. Our algorithm actually solves a more general version of the open problem. Further, as a byproduct of our approach, we present an $O(n\log n + k)$-time algorithm for computing the extended visibility graph of a set of $n$ (possibly intersecting) convex pseudodisks in the plane. The previously best known time bound for this visibility problem is $O(n^2 \log n)$.

Snap rounding is a popular method for rounding the vertices of a planar arrangement of line segments to the integer grid. It has many advantages, including minimum perturbation of the segments, preservation of the arrangement topology, and ease of implementation. However, snap rounding has one significant weakness: it is not stable (i.e., not idempotent). That is, applying snap rounding to a snap-rounded arrangement of n segments may cause additional segment perturbation, and the number of iterations of snap rounding needed to reach stability may be as large as Θ(n2).

We investigate the complexity of shortest paths in time-dependent graphs, in which the costs of edges vary as a function of time, and as a result the shortest path between two nodes s and d can change over time. Our main result is that when the edge cost functions are (polynomial-size) piecewise linear, the shortest path from s to d can change nΘ(log n) times, settling a several-year-old conjecture of Dean [Technical Reports, 1999, 2004]. We also show that the complexity is polynomial if the slopes of the linear function come from a restricted class, present an output-sensitive algorithm for the general case, and describe a scheme for a (1 + ε)-approximation of the travel time function in near-quadratic space. Finally, despite the fact that the arrival time function may have superpolynomial complexity, we show that a minimum delay path for any departure time interval can be computed in polynomial time.

on Computational Geometry took place at Aarhus University in Aarhus, Denmark, in June 2009.The conference program was very strong; from that program I have selected nine outstanding papers for presentation in this special issue.The papers were revised and carefully reviewed according to the high standards of Discrete & Computational Geometry.The nine papers in this issue reflect the diversity of the field of computational geometry: they include algorithmic and lower bound results, practical algorithms with experimentally verified performance and deep explorations of the boundaries of Asymptopia, results for the plane and for high-dimensional spaces, and topics ranging from classical convex hulls to rigidity theory to topological persistence.Several of the papers describe significant breakthroughs, resolving long-open questions in their areas.Andrea Vattani analyzes the performance of the popular k-means algorithm.Although the algorithm works well in practice, Vattani shows that there are configurations of input points that require exponentially many iterations for the algorithm to converge, even in the plane.Vattani's lower bound strengthens previous bounds substantially, from 2 Ω( √ n) to 2 Ω(n) .Csaba Tóth resolves a long-standing open problem about the worst-case complexity of planar binary space partitions (BSPs).For any set of disjoint line segments in the plane, Tóth shows how to construct an autopartition (a BSP built by extending the given segments) whose total complexity is O(n log n log log n ).This upper bound matches the lower bound for the problem and settles a question that had been open for 20 years.

We consider the problem of reconstructing a road network from a collection of path traces and provide guarantees on the accuracy of the reconstruction under reasonable assumptions. Our algorithm can be used to process a collection of polygonal paths in the plane so that shared structures (subpaths) among the paths in the collection can be discovered and the collection can be organized to allow efficient path similarity queries against new query paths on the same road network. This is a timely problem, as GPS and other location traces of both people and vehicles are becoming available on a large scale and there is a real need to create appropriate data structures and data bases for such data.

We consider the problem of approximating a family of isocontours in a sensor fleld with a topologically-equivalent family of simple polygons. Our algorithm is simple and distributed, it gracefully adapts to any user-specified representation size k, and it delivers a worst-case guarantee for the quality of approximation. In particular, we prove that the topology-respecting Hausdorff error in our k -vertex approximation is within a small constant factor of the optimal error possible with Θ(k/log m) vertices, where m is the number of contours. Evaluation of the algorithm on real data suggests that the size increase factor in practice is a constant near 2 .6, and shows no error increase. Our simulation results using a variety of synthetic and real data show that the algorithm smoothly handles complex isocontours, even for representation sizes as small as 32 or 48. Because isocontours are widely used to represent and communicate bi-variate signals, our technique is broadly applicable to innetwork aggregation and summarization of spatial data in sensor networks.

We study the problem of aggregating data from a sparse set of nodes in a wireless sensor network. This is a common situation when a sensor network is deployed to detect relatively rare events. In such situations, each node that should participate in the aggregation knows this fact based on its own sensor readings, but there is no global knowledge in the network of where all these interesting nodes are located. Instead of blindly querying all nodes in the network, we show how the interesting nodes can autonomously discover each other in a distributed fashion and form an ad hoc aggregation structure that can be used to compute cumulants, moments, or other statistical summaries. Key to our approach is the capability for two nodes that wish to communicate at roughly the same time to discover each other at a cost that is proportional to their network distance. We show how to build nearly optimal aggregation structures that can further deal with network volatility and compensate for the loss or duplication of data by exploiting probabilistic techniques.

We describe a new algorithm to enumerate the k shortest simple (loopless) paths in a directed graph and report on its implementation. Our algorithm is based on a replacement paths algorithm proposed by Hershberger and Suri [2001], and can yield a factor Θ( n ) improvement for this problem. But there is a caveat: The fast replacement paths subroutine is known to fail for some directed graphs. However, the failure is easily detected, and so our k shortest paths algorithm optimistically uses the fast subroutine, then switches to a slower but correct algorithm if a failure is detected. Thus, the algorithm achieves its Θ( n ) speed advantage only when the optimism is justified. Our empirical results show that the replacement paths failure is a rare phenomenon, and the new algorithm outperforms the current best algorithms; the improvement can be substantial in large graphs. For instance, on GIS map data with about 5,000 nodes and 12,000 edges, our algorithm is 4--8 times faster. In synthetic graphs modeling wireless ad hoc networks, our algorithm is about 20 times faster.

We prove superlinear lower bounds for some shortest path problems in directed graphs, where no such bounds were previously known. The central problem in our study is the replacement paths problem: Given a directed graph G with non-negative edge weights, and a shortest path P = {e1, e2, …, ep} between two nodes s and t, compute the shortest path distances from s to t in each of the p graphs obtained from G by deleting one of the edges ei. We show that the replacement paths problem requires Ω(m √n) time in the worst case whenever m = O(n √n). Our construction also implies a similar lower bound on the k shortest simple paths problem for a broad class of algorithms that includes all known algorithms for the problem. To put our lower bound in perspective, we note that both these problems (replacement paths and k shortest simple paths) can be solved in near-linear time for undirected graphs.

We consider the following problem: given an on-line, possibly unbounded stream of two-dimensional points, how can we summarize its spatial distribution or shape using a small, bounded amount of memory? We propose a novel scheme, called ClusterHull, which represents the shape of the stream as a dynamic collection of convex hulls, with a total of at most m vertices, where m is the size of the memory. The algorithm dynamically adjusts both the number of hulls and the number of vertices in each hull to best represent the stream using its fixed memory budget. This algorithm addresses a problem whose importance is increasingly recognized, namely the problem of summarizing real-time data streams to enable on-line analytical processing. As a motivating example, consider habitat monitoring using wireless sensor networks. The sensors produce a steady stream of geographic data, namely, the locations of objects being tracked. In order to conserve their limited resources (power, bandwidth, storage), the sensors can compute, store, and exchange ClusterHull summaries of their data, without losing important geometric information. We are not aware of other schemes specifically designed for capturing shape information in geometric data streams, and so we compare ClusterHull with some of the best general-purpose clustering schemes such as CURE, k-median, and LSEARCH. We show through experiments that ClusterHull is able to represent the shape of two-dimensional data streams more faithfully and flexibly than the stream versions of these clustering algorithms.

This paper presents new algorithms for snap rounding an arrangement A of line segments in the plane. Snap rounding defines a set of hot pixels, which are unit squares centered on the integer grid points closest to the vertices of A. Snap rounding simplifies A by replacing every input segment by a piecewise linear curve connecting the centers of the hot pixels the segment intersects. Let H be the set of all hot pixels, and for each A∈H let (h) be the number of segments with an intersection or endpoint inside h. If A contains n input segments, the running time of the first new algorithm is O(Εh∈H is (h) log n). This improves previous input- and output-sensitive algorithms by a factor of Θ(n) in the worst case. The second algorithm has an even better running time of O(Εh∈H ed (h) log n); here ed(h) is the description complexity of the crossing pattern in h, which may be substantially less than is(h) and is never greater.

Recently there has been a growing interest in detecting patterns and analyzing trends in data that are generated continuously, often delivered in some fixed order and at a rapid rate, in the form of a data stream [5, 6]. When the stream consists of spatial data, its geometric "shape" can convey important qualitative aspects of the data set more effectively than many numerical statistics. In a stream setting, where the data must be constantly discarded and compressed, special care must be taken to ensure that the compressed summary faithfully captures the overall shape of the point distribution. We propose a novel scheme, ClusterHulls, to represent the shape of a stream of two-dimensional points. Our scheme is particularly useful when the input contains clusters with widely varying shapes and sizes, and the boundary shape, orientation, or volume of those clusters may be important in the analysis.

Heavy hitters, which are items occurring with frequency above a given threshold, are an important aggregation and summary tool when processing data streams or data warehouses. Hierarchical heavy hitters (HHHs) have been introduced as a natural generalization for hierarchical data domains, including multi-dimensional data. An item x in a hierarchy is called a ϕ-HHH if its frequency after discounting the frequencies of all its descendant hierarchical heavy hitters exceeds ϕn, where ϕ is a user-specified parameter and n is the size of the data set. Recently, single-pass schemes have been proposed for computing ϕ-HHHs using space roughly O(1/ϕ log(ϕn)). The frequency estimates of these algorithms, however, hold only for the total frequencies of items, and not the discounted frequencies; this leads to false positives because the discounted frequency can be significantly smaller than the total frequency. This paper attempts to explain the difficulty of finding hierarchical heavy hitters with better accuracy. We show that a single-pass deterministic scheme that computes ϕ-HHHs in a d-dimensional hierarchy with any approximation guarantee must use Ω(1/ϕd+1) space. This bound is tight: in fact, we present a data stream algorithm that can report the ϕ-HHHs without false positives in O(1/ϕd+1) space.

We propose a new routing graph, the restricted Delaunay graph (RDG), for mobile ad hoc networks. Combined with a node clustering algorithm, the RDG can be used as an underlying graph for geographic routing protocols. This graph has the following attractive properties: 1) it is planar; 2) between any two graph nodes there exists a path whose length, whether measured in terms of topological or Euclidean distance, is only a constant times the minimum length possible; and 3) the graph can be maintained efficiently in a distributed manner when the nodes move around. Furthermore, each node only needs constant time to make routing decisions. We show by simulation that the RDG outperforms previously proposed routing graphs in the context of the Greedy perimeter stateless routing (GPSR) protocol. Finally, we investigate theoretical bounds on the quality of paths discovered using GPSR.

We consider the problem of constructing binary space partitions (BSPs) for orthogonal subdivisions (space-filling packings of boxes) in d-space. We show that a subdivision with n boxes can be refined into a BSP of size $O(n^{(d+1)/{3}})$ for all $d \geq 3$ and that such a partition can be computed in time ${O(K\log n)}$, where K is the size of the BSP produced. Our upper bound on the BSP size is tight for 3-dimensional subdivisions; in higher dimensions, this is the first nontrivial result for general full-dimensional boxes. We also present a lower bound construction for a subdivision of n boxes in d-space for which every axis-aligned BSP has $\Omega(n^{\beta(d)})$ size, where $\beta(d)$ converges to $(1+\sqrt{5})/2$ as $d \rightarrow \infty$.

We consider the problem of constructing binary space partitions (BSPs) for orthogonal subdivisions (space filling packings of boxes) in d-space. We show that a subdivision with n boxes can be refined into a BSP of size O(n d+1/3), for all d ≥ 3, and that such a partition can be computed in time O(K log n), where K is the size of the BSP produced. Our upper bound on the BSP size is tight for 3-dimensional subdivisions in higher dimensions, this is the first nontrivial result for general full-dimensional boxes. We also present a lower bound construction for a subdivision of n boxes in d-space that requires a BSP of size Ω(n946;(d)), where β(d) converges to (1+ √5 )/2 as d → ∞.

We address the problem of distributed information aggregation and storage in a sensor network, where queries can be injected anywhere in the network. The principle we propose is that a sensor should know a "fraction" of the information from distant parts of the network, in an exponentially decaying fashion by distance. We show how a sampled scalar field can be stored in this distributed fashion, with only a modest amount of additional storage and network traffic. Our storage scheme makes neighboring sensors have highly correlated world views; this allows smooth information gradients and enables local search algorithms to work well. We study in particular how this principle of fractionally cascaded information can be exploited to answer range queries about the sampled field efficiently. Using local decisions only we are able to route the query to exactly the portions of the field where the sought information is stored. We provide a rigorous theoretical analysis showing that our scheme is close to optimal.

Geometric coordinates are an integral part of many data streams. Examples include sensor locations in environmental monitoring, vehicle locations in traffic monitoring or battlefield simulations, scientific measurements of earth or atmospheric phenomena, etc. How can one summarize such data streams using limited storage so that many natural geometric queries can be answered faithfully? Some examples of such queries are: report the smallest convex region in which a chemical leak has been sensed, or track the diameter of the dataset. One can also pose queries over multiple streams: track the minimum distance between the convex hulls of two data streams; or report when datasets A and B are no longer linearly separable.In this paper, we propose an adaptive sampling scheme that gives provably optimal error bounds for extremal problems of this nature. All our results follow from a single technique for computing the approximate convex hull of a point stream in a single pass. Our main result is this: given a stream of two-dimensional points and an integer r, we can maintain an adaptive sample of at most 2r + 1 points such that the distance between the true convex hull and the convex hull of the sample points is O(D/r2), where D is the diameter of the sample set. With our sample convex hull, all the queries mentioned above can be answered in either O(log r) or O(r) time.

We propose a simple, deterministic kinetic data structure (KDS) for maintaining a covering of moving points by axis-aligned unit boxes in Rd. The number of boxes is always within a factor of 3d of the best possible static covering. In the plane, this approximation factor (9) compares favorably with the approximation factor (around one million) of the best previous algorithm. The new KDS is efficient, local, compact, and responsive.

A naive algorithm for the replacement paths problem runs in O(n(m+n logn)) time, executing the single-source shortest path algorithm up to n times. In our paper [3], we claimed that the replacement paths problem can be solved inO(m+n logn) time for both undirected and directed graphs. However, there is a flaw that invalidates the algorithm for directed graphs. (The algorithm for undirected graphs remains valid.) The same bound for undirected graphs is also achieved by Nardelli, Proietti, and Widmayer [6], who solve the most vital node problem with an algorithm that also solves the replacement paths problem. Their work is in turn based on earlier work by Malik, Mittal and Gupta [5], Ball, Golden, and Vohra [1] and BarNoy, Khuller, and Schieber [2]. The error in our algorithm for directed graphs led us to investigate the hardness of the replacement paths problem and other related problems. We have recently established lower bounds that show that no replacement paths algorithm of a certain class (including all known algorithms) can achieve the running time of the algorithm for undirected graphs [4]. The mistake in the directed graph algorithm of [3] occurs on page 257, just after Lemma 2, where we say “A simple corollary of this lemma is the fact that if (u; v) is the single edge of path(x; y; G n e) in E(Vx; Vy), then

\emph{We propose a new randomized algorithm for maintaining a set of c lusters among moving nodes in the plane. Given a specified cluster radius, our algorithm selects and maintains a variable subset of the nodes as cluster centers. This subset has the property that (1) balls of the given radius centered at the chosen nodes cover all the others and (2) the number of centers selected is a constant-factor approximation of the minimum possible. As the nodes move, an event-based kinetic data structure updates the clustering as necessary. This kinetic data structure is shown to be responsive, efficient, local, and compact. The produced cover is also smooth, in the sense that wholesale cluster re-arrangements are avoided. The algorithm can be implemented without exact knowledge of the node positions, if each node is able to sense its distance to other nodes up to the cluster radius. Such a kinetic clustering can be used in numerous applications where mobile devices must be interconnected into an ad-hoc network to collaboratively perform some task.}

We solve a shortest path problem that is motivated by recent interest in pricing networks or other computational resources. Informally, how much is an edge in a network worth to a user who wants to send data between two nodes along a shortest path? If the network is a decentralized entity, such as the Internet, in which multiple self-interested agents own different parts of the network, then auction-based pricing seems appropriate. A celebrated result from auction theory shows that the use of Vickrey pricing motivates the owners of the network resources to bid truthfully. In Vickrey's scheme, each agent is compensated in proportion to the marginal utility he brings to the auction. In the context of shortest path routing, an edge's utility is the value by which it lowers the length of the shortest path, i.e., the difference between the shortest path lengths with and without the edge. Our problem is to compute these marginal values for all the edges of the network efficiently. The naive method requires solving the single-source shortest path problem up to n times, for an n-node network. We show that the Vickrey prices for all the edges can be computed in the same asymptotic time complexity as one single-source shortest path problem. This solves an open problem posed by N. Nisan and A. Ronen (1999).

We propose a new routing graph, the Restricted Delaunay Graph (RDG), for ad hoc networks. Combined with a node clustering algorithm RDG can be used as an underlying graph for geographic routing protocols. This graph has the following attractive properties: (1) it is a planar graph; (2) between any two nodes there exists a path in the RDG whose length, whether measured in terms of topological or Euclidean distance, is only a constant times the optimum length possible; and (3) the graph can be maintained efficiently in a distributed manner when the nodes move around. Furthermore, each node only needs constant time to make routing decisions. We also show by simulation that the RDG outperforms the previously proposed routing graphs under the Greedy Perimeter Stateless Routing (GPSR) protocol. In addition, we investigate theoretical bounds on the quality of paths discovered using GPSR

We describe a kinetic data structure (KDS) that maintains the connected components of the union of a set of unit-radius disks moving in the plane. We assume that the motion of each disk can be specified by a low-degree algebraic trajectory; this trajectory, however, can be modified in an on-line fashion. While the disks move continuously, their connectivity changes at discrete times. Our main result is an O(n) space data structure that takes O(log n/ log log n) time per connectivity query of the form "are disks A and B in the same connected component?" A straightforward approach based on dynamically maintaining the overlap graph requires## n 2 ) space. Our data structure requires only linear space and must deal with O(n 2+# ) updates in the worst case, each requiring O(log 2 n) amortized time. This number of updates is close to optimal, since a set of n moving unit disks can undergo## n 2 ) connectivity changes. 1 Introduction Motivated by applications in mobile ...

IntroductionWe revisit the notion of kinetic efficiency for noncanonically-defined discrete attributes of moving data, like binary space partitions and triangulations.Under very general computational models, we obtain lower bounds on the minimum amount of work required to maintain any binary space partition of moving segments in the plane or any Steiner triangulation of moving points in the plane.Such lower bounds-the first to be obtained in the kinetic context-are necessary to evaluate the efliciency of kinetic data structures when the attribute to be maintained is not canonically defined.

No abstract available.

We develop a kinetic data structure (KDS) for maintaining the connectivity of a set of axis-aligned rectangles moving in the plane. In the kinetic framework, each rectangle is assumed to travel along a low-degree algebraic path, specified by a flight plan---if the flight plan changes, the data structure is informed about it. The connectivity of rectangles changes only at discrete moments, given by the times when the order of rectangles along either axis changes. Our main result is a kinetic data structure of size O(n log n) that requires O(log 2 n) amortized time for each update, and answers connectivity queries in worst-case time O(log n= log log n). 1 Introduction Connectivity is the most basic of graph properties, with many applications to real-world problems. Applications of connectivity range from electrical connectivity in integrated circuits to network connectivity in communication networks. In this paper, we explore the problem of maintaining the connectivity of n axis-alig...

We propose an optimal-time algorithm for a classical problem in plane computational geometry: computing a shortest path between two points in the presence of polygonal obstacles. Our algorithm runs in worst-case time O(n log n) and requires O(n log n) space, where n is the total number of vertices in the obstacle polygons. The algorithm is based on an efficient implementation of wavefront propagation among polygonal obstacles, and it actually computes a planar map encoding shortest paths from a fixed source point to all other points of the plane; the map can be used to answer single-source shortest path queries in O(log n) time. The time complexity of our algorithm is a significant improvement over all previously published results on the shortest path problem. Finally, we also discuss extensions to more general shortest path problems, involving nonpoint and multiple sources.

We study the problem of robustly rounding a set S of n line segments in R2 using the snap rounding paradigm.In this paradigm each pixel containing an endpoint or intersection point is called "hot," and all segments intersecting a hot pixel are re-routed to pass through its center.We show that a snap-rounded approximation to the arrangement defined by S can be built in an output-sensitive fashion, and that this can be done without first determining all the intersecting pairs of segments in S. Specifically, we give a deterministic plan~sweep algorithm running in time O(n bgn -F &H Ihl10g ~), where ~is the set of hot pixela and \hl is the number of segments intersecting a hot pixel h E H. We alsogive a simple randomized incremental construction whose expected running time matches that of our deterministic algorithm.The complexity of these algorithms is optimal up to polylogarithmic factors.

Article Efficient breakout routing in printed circuit boards Share on Authors: John Hershberger Mentor Graphics, 1001 Ridder Park Drive, San Jose, CA Mentor Graphics, 1001 Ridder Park Drive, San Jose, CAView Profile , Subhash Suri Department of Computer Science, Washington University, St. Louis, MO Department of Computer Science, Washington University, St. Louis, MOView Profile Authors Info & Claims SCG '97: Proceedings of the thirteenth annual symposium on Computational geometryAugust 1997 Pages 460–462https://doi.org/10.1145/262839.263082Online:01 August 1997Publication History 9citation256DownloadsMetricsTotal Citations9Total Downloads256Last 12 Months5Last 6 weeks2 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

We present an O(n) time algorithm for computing row-wise maxima or minima of an implicit, totally monotone $n \times n$ matrix whose entries represent shortest-path distances between pairs of vertices in a simple polygon. We apply this result to derive improved algorithms for several well-known problems in computational geometry. Most prominently, we obtain linear-time algorithms for computing the geodesic diameter, all farthest neighbors, and external farthest neighbors of a simple polygon, improving the previous best result by a factor of O(log n) in each case.

Any practical model of robotic motion must cope with the uncertainty and imprecision inherent in real robots. One important model is compliant motion, in which a robot that encounters an obstacle obliquely may slide along the obstacle. The authors start by investigating the geometry of compliant motion in the plane under perfect control and find a compact data structure encoding all paths to a goal. When the authors introduce uncertainty in control and position sensing, the same data structure allows them to find efficiently a compliant motion that reaches the goal, if one exists, to compute the boundary of the nondirectional backprojection of the goal, and to compute multistep plans for sensorless robots. This “preprocessing and query” approach has advantages of speed for online queries and flexibility for considering robots with different capabilities or initial positions in the same environment.

In this paper we investigate the problem of morphing (i.e. continuously deforming) one simple polygon into another. We assume that our two initial polygons have the same number of sides n, and that corresponding sides are parallel. We show that a morph is always possible by a varying simple interpolating polygon also of n sides parallel to those of the two original ones. If we consider a uniform scaling or translation of part of the polygon as an atomic morphing step, then we show that O(n4/3+ε) such steps are sufficient for the morph.

No abstract available.

A collection of geometric selection lemmas is proved, such as the following: For any set P of n points in three-dimensional space and any set S of m spheres, where each sphere passes through a distinct point pair in P, there exists a point x, not necessarily in P, that is enclosed by $\Omega ({{m^2 } / {(n^2 \log ^6 \tfrac{{n^2 }}{m})}})$ of the spheres in S. Similar results apply in arbitrary fixed dimensions, and for geometric bodies other than spheres. The results have applications in reducing the size of geometric structures, such as three-dimensional Delaunay triangulations and Gabriel graphs, by adding extra points to their defining sets.

No abstract available.

We propose a new algorithm for a classical problem in plane computational geometry: computing a shortest path between two points in the presence of polygonal obstacles. Our algorithm runs in worst-case time O(nlog/sup 2/ n) and requires O(nlog n) space, where n is the total number of vertices in the obstacle polygons. Our algorithm actually computes a planar map that encodes shortest paths from a fixed source point to all other points of the plane; the map can be used to answer single-source shortest path queries in O(log n) time. The time complexity of our algorithm is a significant improvement over all previous results known for the shortest path problem.>

We present an O(n) time algorithm for computing row-wise maxima or minima of an implicit, totally-monotone n \\Theta n matrix whose entries represent shortest-path distances between pairs of vertices in a simple polygon. We apply this result to derive improved algorithms for several well-known problems in computational geometry. Most prominently, we obtain linear-time algorithms for computing the geodesic diameter, all farthest neighbors, and external farthest neighbors of a simple polygon, improving the previous best result by a factor of O(logn) in each case. Key Words: Shortest paths, matrix searching, geodesic diameter, farthest neighbors, geometric matching. 1 1 Introduction Matrix-searching is the popular term for a technique introduced by Aggarwal et al. [2] for computing row-wise maxima in a totally monotone matrix. A matrix M is called totally monotone if M(i; k) ! M(i; l) =) M(j; k) ! M(j; l); for any i ! j and k ! l. Aggarwal et al. [2] discovered the importance o...

We provide optimal parallel solutions to several shortest path and visibility problems set in triangulated simple polygons. Let P be a triangulated simple polygon with n vertices, preprocessed to support shortest path queries. We can find the shortest path tree from any point inside P in O(log n) time using O(n/log n) processors. In the same bounds, we can preprocess P for shooting queries (a query can be answered in O(log n0 time by a uniprocessor). Given a set S of m points inside P, we can find an implicit representation of the relative convex hull of S in O(log(nm)) time with O(k/log(nm)) processors. All of these algorithms are deterministic and use the CREW PRAM model.

We show that for any set Π of n points in three-dimensional space there is a set Q of 𝒪(n1/2 log3 n) points so that the Delaunay triangulation of Π ∪ Q has at most 𝒪(n3/2 log3 n) edges — even though the Delaunay triangulation of Π may have Ω(n2) edges. The main tool of our construction is the following geometric covering result: For any set Π of n points in three-dimensional space and any set S of m spheres, where each sphere passes through a distinct point pair in Π, there exists a point x, not necessarily in Π, that is enclosed by Ω(m2/n2 log3 n2/m) of the spheres in S.

We consider motion planning under the compliant motion model, in which a robot directed to walk into a wall may slide along it. We examine several variants of compliant motion planning for a point robot inside a simple polygon with n sides, where the goal is a fixed vertex or edge. For the case in which the robot moves with perfect control, we build a data structure that lets us in Ο(log n) time determine the range of directions in which the robot can move from a query point to the goal in a single step. This structure lets us solve a variety of other problems: we can find a similar query data structure for multi-step paths; we can solve single-step problems allowing uncertainty in control and position sensing; and we can explicitly compute the set of all points that can reach the goal in a single step, even allowing uncertainty in control. Our algorithms run in Ο(n log n) time and linear space; they use a novel method for maintaining convex hulls of simple paths that may be of independent interest.

We consider the following problem: given a planar set of points S, a measure μ acting on S, and a pair of values μ1 and μ2, does there exist a bipartition S = S1 U S2 satisfying μ(Si) ≤ μi for i = 1,2? We present algorithms of complexity Ο(n log n) for several natural measures, including the diameter (set measure), the area, perimeter or diagonal of the smallest enclosing axes-parallel rectangle (rectangular measure), and the side length of the smallest enclosing axes-parallel square (square measure). The problem of partitioning S into k subsets, where k ≥ 3, is known to be NP-complete for many of these measures.

We consider arrangements of curves that intersect pairwise in at most k points. We show that a curve can sweep any such arrangement and maintain the k-intersection property if and only if k equals 1 or 2. We apply this result to an eclectic set of problems: finding Boolean formulae for polygons with curved edges, counting triangles and digons in arrangements of pseudocircles, and finding extension curves for arrangements. We also discuss implementing the sweep.

Let P be a simple polygon with n sides. This paper shows how to preprocess the polygon so that, given two query points p and q inside P, the length of the shortest path inside the polygon from p to q can be found in time O(log n). The path itself must be polygonal and can be extracted in additional time proportional to the number of turns it makes. The preprocessing consists of triangulation plus a linear amount of additional work.

Motivated by a number of motion-planning questions, we investigate in this paper some general topological and combinatorial properties of the boundary of the union of n regions bounded by Jordan curves in the plane. We show that, under some fairly weak conditions, a simply connected Riemann surface can be constructed that exactly covers this union and whose boundary has combinatorial complexity that is nearly linear, even though the covered region can have quadratic complexity. In the case where our regions are delimited by Jordan arcs in the upper halfplane starting and ending on the x-axis such that any pair of arcs intersect in at most three points, we prove that the total number of subarcs that appear on the boundary of the union is only Θ(nα(n)), where α(n) is the extremely slowly growing functional inverse of Ackermann's function.

An arrangement of n lines (or line segments) in the plane is the partition of the plane defined by these objects. Such an arrangement consists of Ο(n2) regions, called faces. In this paper we study the problem of calculating and storing arrangements implicitly, using subquadratic space and preprocessing, so that, given any query point p, we can calculate efficiently the face containing p. First, we consider the case of lines and show that with Λ(n) space1 and Λ(n3/2) preprocessing time, we can answer face queries in Λ(√n) + Ο(K) time, where K is the output size. (The query time is achieved with high probability.) In the process, we solve three interesting subproblems: 1) given a set of n points, find a straight-edge spanning tree of these points such that any line intersects only a few edges of the tree, 2) given a simple polygonal path Γ, form a data structure from which we can find the convex hull of any subpath of Γ quickly, and 3) given a set of points, organize them so that the convex hull of their subset lying above a query line can be found quickly. Second, using random sampling, we give a trade-off between increasing space and decreasing query time. Third, we extend our structure to report faces in an arrangement of line segments in Λ(n1/3) time, given Λ(n4/3) space and Λ(n5/3) preprocessing time.

We consider the problem of converting boundary representations of polyhedral objects into constructive-solid-geometry (CSG) representations. The CSG representations for a polyhedron P are based on the half-spaces supporting the faces of P. For certain kinds of polyhedra this problem is equivalent to the corresponding problem for simple polygons in the plane. We give a new proof that the interior of each simple polygon can be represented by a monotone boolean formula based on the half-planes supporting the sides of the polygon and using each such half-plane only once. Our main contribution is an efficient and practical O(n log n) algorithm for doing this boundary-to-CSG conversion for a simple polygon of n sides. We also prove that such nice formulæ do not always exist for general polyhedra in three dimensions.

Let P be a simple polygon with n sides. This paper shows how to preprocess the polygon so that, given two query points p and q inside P, the length of the shortest path inside the polygon from p to q can be found in time Ο(log n). The path itself must be polygonal and can be extracted in additional time proportional to the number of turns it makes. The preprocessing consists of triangulation plus a linear amount of additional work.

Let P be a given simple polygon with n sides. The visibility graph of P has an edge between every pair of polygon vertices that can be connected by an open segment in the interior of P. We describe an algorithm that finds the visibility graph of P in O(m + n log log n) time, where m is the number of edges in the visibility graph. Because m can be as small as O(n), the algorithm improves on the more general visibility algorithms of Asano et al. [AAGHI] and Welzl [W], which take T(n2) time.

We present linear time algorithms for solving the following problems involving a simple planar polygon P: (i) Computing the collection of all shortest paths inside P from a given source vertex s to all the other vertices of P; (ii) Computing the subpolygon of P consisting of points that are visible from a segment within P; (iii) Preprocessing P so that for any query ray r emerging from some fixed edge e of P, we can find in logarithmic time the first intersection of r with the boundary of P; (iv) Preprocessing P so that for any query point x in P, we can find in logarithmic time the portion of the edge e that is visible from x; (v) Preprocessing P so that for any query point x inside P and direction u, we can find in logarithmic time the first point on the boundary of P hit by the ray at direction u from x; (vi) Calculating a hierarchical decomposition of P into smaller polygons by recursive polygon cutting, as in [Ch]. (vii) Calculating the (clockwise and counterclockwise) “convex ropes” (in the terminology of [PS]) from a fixed vertex s of P lying on its convex hull, to all other vertices of P. All these algorithms are based on a recent linear time algorithm of Tarjan and Van Wyk for triangulating a simple polygon, but use additional techniques to make all subsequent phases of these algorithms also linear.

Consider a collection of disjoint polygons in the plane containing a total of n edges. We show how to build, in O(n2) time and space, a data structure from which in O(n) time we can compute the visibility polygon of a given point with respect to the polygon collection. As an application of this structure, the visibility graph of the given polygons can be constructed in O(n2) time and space. This implies that the shortest path that connects two points in the plane and avoids the polygons in our collection can be computed in O(n2) time, improving earlier O(n2 log n) results.