The classic Watchman Route Problem (WRP) seeks to compute a shortest tour in a polygonal domain that sees every point of the domain. We introduce and study a novel generalization of the WRP, the See-Through Watchman Route Problem (STWRP), in which, in addition to vision-blocking "walls" of an input domain, there are obstacles to motion that are not opaque to vision: the watchman can see through certain obstacles or portions of the boundary of a polygonal domain P. This setting is motivated by real-world situations that may include transparent barriers (e.g., glass walls), obstacles that obstruct movement but not vision (e.g., lakes, flowerbeds, or potholes), and robotic sensors with penetration capabilities (e.g., microwave imaging). To the best of our knowledge, this version of the problem is new to the algorithms community. Our main result is an FPTAS for the STWRP in the case that P is an opaque-walled simple polygon having within it a set of transparent obstacles. A closely related problem that arises in this setting is that of the Traveling Salesperson problem with neighborhoods (TSPN) on a set of lines in the plane, with obstacles. We give the first FPTAS for the Quota-TSPN on infinite lines with polygonal obstacles. Additionally, we show tightness of our FPTAS, in that the Quota-TSPN on infinite lines with obstacles is weakly NP-hard. In the case of the STWRP within a simple polygon P with portions of the boundary, ∂ P, being transparent, we prove that the problem is NP-hard to approximate within a factor better than O(log n).

We introduce the contiguous art gallery problem which is to guard the boundary of a simple polygon with a minimum number of guards such that each guard covers exactly one contiguous portion of the boundary. Art gallery problems are often NP-hard. In particular, it is NP-hard to minimize the number of guards to see the boundary of a simple polygon, without the contiguity constraint. This paper is a merge of three concurrent works [Ahmad Biniaz et al., 2024; Magnus Christian Ring Merrild et al., 2024; Eliot W. Robson et al., 2024] each showing that (surprisingly) the contiguous art gallery problem is solvable in polynomial time. The common idea of all three approaches is developing a greedy function that maps a point on the boundary to the furthest point on the boundary so that the contiguous interval along the boundary between them could be guarded by one guard. Repeatedly applying this function immediately leads to an OPT+1 approximation. By studying this greedy algorithm, we present three different approaches that achieve an optimal solution. The first and second approach apply this greedy algorithm from different points on the boundary that could be found in advance or on the fly while traversing along the boundary (respectively). The third approach represents this function as a piecewise linear rational function, which can be reduced to an abstract arc cover problem involving infinite families of arcs. We identify other problems that can be represented by similar functions, and solve them via the third approach. From the combinatorial point of view, we show that any n-vertex polygon can be guarded by at most ⌊(n-2)/2⌋ guards. This bound is tight because there are polygons that require this many guards.

In case of a future pandemic, the mobility dynamics of a city can be controlled by intervening in the mobility patterns of people. Instead of hard quarantine policies, incentives can be designed that are compatible with people's preferences. At first, we distinguish mobility from the different types of locations for which distance matters. We match these types of locations in a way that maximizes the natural preference of people to visit the locations. We investigate different approaches for matching locations, such as retail and educational services, while considering people's preferences. We show that satisfying the preferences of the entire city is a computationally hard problem. Approximation algorithms are proposed in which the penalty for preference violation is bounded. We propose a fast approximation algorithm that focuses on the penalty value of locations, and we propose a more computationally heavy approximation that focuses on user penalty with a specific scheme of user allocation to locations. Additionally, we investigated higher-order matching of locations and the complexity of urban partitioning. We tested our approach in Euclidean space and network space. Finally, we show that applying such mobility restrictions can reduce the transmission rate, and we extract cells whose people can be incentivized to fulfill their needs based on the proposed algorithms, slowing down a future pandemic and preventing potential superspreading events.

Assume that a target is known to be present at an unknown point among a finite set of locations in the plane. We search for it using a mobile robot that has imperfect sensing capabilities. It takes time for the robot to move between locations and search a location; we have a total time budget within which to conduct the search. We study the problem of computing a search path/strategy for the robot that maximizes the probability of detection of the target. Considering non-uniform travel times between points (e.g., based on the distance between them) is crucial for search and rescue applications; such problems have been investigated to a limited extent due to their inherent complexity. In this paper, we describe fast algorithms with performance guarantees for this search problem and some variants, complement them with complexity results, and perform experiments to characterize their performance.

We investigate the Dispersive Art Gallery Problem with vertex guards and rectangular visibility (r-visibility) for a class of orthogonal polygons that reflect the properties of real-world floor plans: these office-like polygons consist of rectangular rooms and corridors. In the dispersive variant of the Art Gallery Problem, the objective is not to minimize the number of guards but to maximize the minimum geodesic L₁-distance between any two guards, called the dispersion distance. Our main contributions are as follows. We prove that determining whether a vertex guard set can achieve a dispersion distance of 4 in office-like polygons is NP-complete, where vertices of the polygon are restricted to integer coordinates. Additionally, we present a simple worst-case optimal algorithm that guarantees a dispersion distance of 3 in polynomial time. Our complexity result extends to polyominoes, resolving an open question posed by Rieck and Scheffer [Christian Rieck and Christian Scheffer, 2024]. When vertex coordinates are allowed to be rational, we establish analogous results, proving that achieving a dispersion distance of 2+ε is NP-hard for any ε > 0, while the classic Art Gallery Problem remains solvable in polynomial time for this class of polygons. Furthermore, we give a straightforward polynomial-time algorithm that computes worst-case optimal solutions with a dispersion distance 2. On the other hand, for the more restricted class of hole-free independent office-like polygons, we propose a dynamic programming approach that computes optimal solutions. Moreover, we demonstrate that the problem is practically tractable for arbitrary orthogonal polygons. To this end, we compare solvers based on SAT, CP, and MIP formulations. Notably, SAT solvers efficiently compute optimal solutions for randomly generated instances with up to 1600 vertices in under 15s.

Motivated by the problem of estimating bottleneck capacities on the Internet, we formulate and study the problem of vantage point selection. We are given a graph G = (V, E) whose edges E have unknown capacity values that are to be discovered. Probes from a vantage point, i.e, a vertex v ∈ V, along shortest paths from v to all other vertices, reveal bottleneck edge capacities along each path. Our goal is to select k vantage points from V that reveal the maximum number of bottleneck edge capacities. We consider both a non-adaptive setting where all k vantage points are selected before any bottleneck capacity is revealed, and an adaptive setting where each vantage point selection instantly reveals bottleneck capacities along all shortest paths starting from that point. In the non-adaptive setting, by considering a relaxed model where edge capacities are drawn from a random permutation (which still leaves the problem of maximizing the expected number of revealed edges NP-hard), we are able to give a 1-1/e approximate algorithm. In the adaptive setting we work with the least permissive model where edge capacities are arbitrarily fixed but unknown. We compare with the best solution for the particular input instance (i.e. by enumerating all choices of k tuples), and provide both lower bounds on instance optimal approximation algorithms and upper bounds for trees and planar graphs.

We propose precise notions of what it means to guard a domain "robustly", under a variety of models. While approximation algorithms for minimizing the number of (precise) point guards in a polygon is a notoriously challenging area of investigation, we show that imposing various degrees of robustness on the notion of visibility coverage leads to a more tractable (and realistic) problem for which we can provide approximation algorithms with constant factor guarantees.

Given a simple polygon P, the minimum convex cover problem seeks to cover P with the fewest convex polygons that lie within P. The maximum hidden set problem seeks to place within P a maximum cardinality set of points no two of which see each other. We give constant factor approximation algorithms for both problems. Previously, the best approximation factor for the minimum convex cover was logarithmic; for the maximum hidden set problem, no approximation algorithm was known.

The classical and extensively-studied Fréchet distance between two curves is defined as an inf max, where the infimum is over all traversals of the curves, and the maximum is over all concurrent positions of the two agents. In this article we investigate a "flipped" Fréchet measure defined by a sup min - the supremum is over all traversals of the curves, and the minimum is over all concurrent positions of the two agents. This measure produces a notion of "social distance" between two curves (or general domains), where agents traverse curves while trying to stay as far apart as possible. We first study the flipped Fréchet measure between two polygonal curves in one and two dimensions, providing conditional lower bounds and matching algorithms. We then consider this measure on polygons, where it denotes the minimum distance that two agents can maintain while restricted to travel in or on the boundary of the same polygon. We investigate several variants of the problem in this setting, for some of which we provide linear time algorithms. Finally, we consider this measure on graphs. We draw connections between our proposed flipped Fréchet measure and existing related work in computational geometry, hoping that our new measure may spawn investigations akin to those performed for the Fréchet distance, and into further interesting problems that arise.

We present a new class of problems where the goal is to select a “fair” subgraph H of a given graph G = (V,E), such that H decomposes into many small components. A subgraph H c G is (P,d) fair if every vertex v ϵ P has the same degree d in H, where P c V and d > 0 are input parameters. These problems arise when the goal is to allow individuals to equally participate in activities in such a way that the connected components within an interaction graph, which models potential interactions among people, are of the smallest possible size, so that the spread of the contagion, and the difficulty of contact tracing in case of infection, is minimized. Within a preference graph that models the set of preferred choices for each individual when selecting among available options of where to conduct any particular type of activity (e.g., which gym to attend), we seek to compute the fair subgraph of assignments of individuals to these options, so that the number of people in each connected component (“interaction community”) of the resulting subgraph is minimized, and everyone is given the same number of options for every activity. We show that the fair subgraph selection problem is NP-hard, even for very restricted versions. We then formulate the problem as an integer program, and give a polynomial time computable lower bound on the optimal solution.

We give a polynomial-time constant-factor approximation algorithm for maximum independent set for (axis-aligned) rectangles in the plane. Using a polynomial-time algorithm, the best approximation factor previously known is$O(\log\log n)$. The results are based on a new form of recursive partitioning in the plane, in which faces that are constant-complexity and orthogonally convex are recursively partitioned into a constant number of such faces.

Motivated by indoor localization by tripwire lasers, we study the problem of cutting a polygon into small-size pieces, using the chords of the polygon. Several versions are considered, depending on the definition of the "size" of a piece. In particular, we consider the area, the diameter, and the radius of the largest inscribed circle as a measure of the size of a piece. We also consider different objectives, either minimizing the maximum size of a piece for a given number of chords, or minimizing the number of chords that achieve a given size threshold for the pieces. We give hardness results for polygons with holes and approximation algorithms for multiple variants of the problem.

Due to increasing concerns of data privacy, databases are being encrypted before they are stored on an untrusted server. To enable search operations on the encrypted data, searchable encryption techniques have been proposed. Representative schemes use order-preserving encryption (OPE) for supporting efficient Boolean queries on encrypted databases. Yet, recent works showed the possibility of inferring plaintext data from OPE-encrypted databases, merely using the order-preserving constraints, or combined with an auxiliary plaintext dataset with similar frequency distribution. So far, the effectiveness of such attacks is limited to single-dimensional dense data (most values from the domain are encrypted), but it remains challenging to achieve it on high-dimensional datasets (e.g., spatial data), which are often sparse in nature. In this paper, for the first time, we study data inference attacks on multi-dimensional encrypted databases (with 2-D as a special case). We formulate it as a 2-D order-preserving matching problem and explore both unweighted and weighted cases, where the former maximizes the number of points matched using only order information and the latter further considers points with similar frequencies. We prove that the problem is NP-hard, and then propose a greedy algorithm, along with a polynomial-time algorithm with approximation guarantees. Experimental results on synthetic and real-world datasets show that the data recovery rate is significantly enhanced compared with the previous 1-D matching algorithm.

We study a trajectory analysis problem we call the Trajectory Capture Problem (TCP), in which, for a given input set T of trajectories in the plane, and an integer k≥ 2, we seek to compute a set of k points ("portals") to maximize the total weight of all subtrajectories of T between pairs of portals. This problem naturally arises in trajectory analysis and summarization. We show that the TCP is NP-hard (even in very special cases) and give some first approximation results. Our main focus is on attacking the TCP with practical algorithm-engineering approaches, including integer linear programming (to solve instances to provable optimality) and local search methods. We study the integrality gap arising from such approaches. We analyze our methods on different classes of data, including benchmark instances that we generate. Our goal is to understand the best performing heuristics, based on both solution time and solution quality. We demonstrate that we are able to compute provably optimal solutions for real-world instances.

Given a set D of n unit disks in the plane and an integer k <= n, the maximum area connected subset problem asks for a set D' subseteq D of size k that maximizes the area of the union of disks, under the constraint that this union is connected. This problem is motivated by wireless router deployment and is a special case of maximizing a submodular function under a connectivity constraint. We prove that the problem is NP-hard and analyze a greedy algorithm, proving that it is a 1/2-approximation. We then give a polynomial-time approximation scheme (PTAS) for this problem with resource augmentation, i.e., allowing an additional set of epsilon k disks that are not drawn from the input. Additionally, for two special cases of the problem we design a PTAS without resource augmentation.

A determinacy race occurs if two or more logically parallel instructions access the same memory location and at least one of them tries to modify its content. Races are often undesirable as they can lead to nondeterministic and incorrect program behavior. A data race is a special case of a determinacy race which can be eliminated by associating a mutual-exclusion lock with the memory location in question or allowing atomic accesses to it. However, such solutions can reduce parallelism by serializing all accesses to that location. For associative and commutative updates to a memory cell, one can instead use a reducer, which allows parallel race-free updates at the expense of using some extra space. More extra space usually leads to more parallel updates, which in turn contributes to potentially lowering the overall execution time of the program. We start by asking the following question. Given a fixed budget of extra space for mitigating the cost of races in a parallel program, which memory locations should be assigned reducers and how should the space be distributed among those reducers in order to minimize the overall running time? We argue that under reasonable conditions the races of a program can be captured by a directed acyclic graph (DAG), with nodes representing memory cells and arcs representing read-write dependencies between cells. We then formulate our original question as an optimization problem on this DAG. We concentrate on a variation of this problem where space reuse among reducers is allowed by routing every unit of extra space along a (possibly different) source to sink path of the DAG and using it in the construction of multiple (possibly zero) reducers along the path. We consider two different ways of constructing a reducer and the corresponding duration functions (i.e., reduction time as a function of space budget). We generalize our race-avoiding space-time tradeoff problem to a discrete resource-time tradeoff problem with general non-increasing duration functions and resource reuse over paths of the given DAG. For general DAGs, we show that even if the entire DAG is available offline the problem is strongly NP-hard under all three duration functions, and we give approximation algorithms for solving the corresponding optimization problems. We also prove hardness of approximation for the general resource-time tradeoff problem and give a pseudo-polynomial time algorithm for series-parallel DAGs.

With the ubiquitous adoption of smartphones and mobile devices, it is now common practice for one's location to be sensed, collected and likely shared through social platforms. While such data can be helpful for many applications, users start to be aware of the privacy issue in handling location and trajectory data. While some users may voluntarily share their location information (e.g., for receiving location-based services, or for crowdsourcing systems), their location information may lead to information leaks about the whereabouts of other users, through the co-location of events when two users are at the same location at the same time and other side information, such as upper bounds of movement speed. It is therefore crucial to understand how much information one can derive about other's positions through the co-location of events and occasional GPS location leaks of some of the users. In this paper we formulate the problem of inferring locations of mobile agents, present theoretically-proven bounds on the amount of information that could be leaked in this manner, study their geometric nature, and present algorithms matching these bounds. We will show that even if a very weak set of assumptions is made on trajectories' patterns, and users are not obliged to follow any 'reasonable' patterns, one could infer very accurate estimation of users' locations even if they opt not to share them. Furthermore, this information could be obtained using almost linear-time algorithms, suggesting the practicality of the method even for huge volumes of data.

In this paper we study a natural special case of the Traveling Salesman Problem (TSP) with point-locational-uncertainty which we will call the adversarial TSP problem (ATSP). Given a metric space (X, d) and a set of subsets R = {R_1, R_2, ... , R_n} : R_i subseteq X, the goal is to devise an ordering of the regions, sigma_R, that the tour will visit such that when a single point is chosen from each region, the induced tour over those points in the ordering prescribed by sigma_R is as short as possible. Unlike the classical locational-uncertainty-TSP problem, which focuses on minimizing the expected length of such a tour when the point within each region is chosen according to some probability distribution, here, we focus on the adversarial model in which once the choice of sigma_R is announced, an adversary selects a point from each region in order to make the resulting tour as long as possible. In other words, we consider an offline problem in which the goal is to determine an ordering of the regions R that is optimal with respect to the ``worst'' point possible within each region being chosen by an adversary, who knows the chosen ordering. We give a 3-approximation when R is a set of arbitrary regions/sets of points in a metric space. We show how geometry leads to improved constant factor approximations when regions are parallel line segments of the same lengths, and a polynomial-time approximation scheme (PTAS) for the important special case in which R is a set of disjoint unit disks in the plane.

Given $n$ pairs of points, $\mathcal{S} = \{\{p_1, q_1\}, \{p_2, q_2\}, \dots, \{p_n, q_n\}\}$, in some metric space, we study the problem of two-coloring the points within each pair, red and blue, to optimize the cost of a pair of node-disjoint networks, one over the red points and one over the blue points. In this paper we consider our network structures to be spanning trees, traveling salesman tours or matchings. We consider several different weight functions computed over the network structures induced, as well as several different objective functions. We show that some of these problems are NP-hard, and provide constant factor approximation algorithms in all cases.

We study the r-gather clustering problem in a mobile and distributed setting. In this problem, nodes must be clustered into groups of at least r nodes each, and the goal is to minimize the diameter of the clusters. This notion of clustering is motivated by protecting user anonymity in location-based services or trajectory publication. Prior works on r-gather problems are centralized and cannot be easily adapted to the mobile setting. We describe a distributed algorithm that produces compact clusters, within an approximation factor 4 of the minimum cluster diameter possible. The algorithm can run on the mobile nodes and access points at the network edge locally, and can handle node mobility, rapidly switching cluster memberships as needed. The distributed approach naturally comes with the advantage of greater resilience and stability. Additionally, we show that it achieves local optimality; i.e., from the point of view of any particular node, the solution is nearly as favorable as possible, irrespective of the global configuration. We also show how to cluster trajectories with dynamic re-groupings. Further, we improve the theoretical hardness results for the problem in the Euclidean setting.

We provide a spectrum of results for the Universal Guard Problem, in which one is to obtain a small set of points ("guards") that are "universal" in their ability to guard any of a set of possible polygonal domains in the plane. We give upper and lower bounds on the number of universal guards that are always sufficient to guard all polygons having a given set of n vertices, or to guard all polygons in a given set of k polygons on an n-point vertex set. Our upper bound proofs include algorithms to construct universal guard sets of the respective cardinalities.

In this paper we investigate sensor deployment and coverage algorithms for using infrared signals in indoor applications. Infrared signals are directional and reliable signals that have little interference with other electromagnetic signals that are commonly found in the deployment domain such as visible light and wireless radio waves. Since the angle of arrival is used, and line of sight is the main constraint for IR signals, we investigate the problem called robust guarding, i.e., placing emitters to ensure that all points of the domain are robustly covered by two emitters that are from sufficiently different directions. We prove combinatorial upper and lower bounds for the number of emitters needed and prove that finding the minimum number of guards is NP-hard. We show that n/2 guards are always sufficient and sometimes necessary for rectilinear polygons and we provide practical algorithms in general. We also developed a testbed with low cost off-the-shelf infrared (IR) emitters and sensors for indoor device-free localization. We tested the algorithms for using infrared sensors for indoor localization and our system achieves an average accuracy of 11.7 cm in a typical office setting.

For a polygonal domain with h holes and a total of n vertices, we present algorithms that compute the L_1 geodesic diameter in O(n^2+h^4) time and the L_1 geodesic center in O((n^4+n^2 h^4)*alpha(n)) time, where alpha(.) denotes the inverse Ackermann function. No algorithms were known for these problems before. For the Euclidean counterpart, the best algorithms compute the geodesic diameter in O(n^{7.73}) or O(n^7(h+log(n))) time, and compute the geodesic center in O(n^{12+epsilon}) time. Therefore, our algorithms are much faster than the algorithms for the Euclidean problems. Our algorithms are based on several interesting observations on L_1 shortest paths in polygonal domains.

In the relay placement problem, the input is a set of sensors and a number r ⩾ 1, the communication range of a relay. In the one-tier version of the problem, the objective is to place a minimum number of relays so that between every pair of sensors there is a path through sensors and/or relays such that the consecutive vertices of the path are within distance r if both vertices are relays and within distance 1 otherwise. The two-tier version adds the restrictions that the path must go through relays, and not through sensors . We present a 3.11-approximation algorithm for the one-tier version and a polynomial-time approximation scheme (PTAS) for the two-tier version. We also show that the one-tier version admits no PTAS, assuming P ≠ NP.

We show how to preprocess a polygonal domain with a fixed starting point s in order to answer efficiently the following queries: Given a point q, how should one move from s in order to see q as soon as possible? This query resembles the well-known shortest-path-to-a-point query, except that the latter asks for the fastest way to reach q, instead of seeing it. Our solution methods include a data structure for a different generalization of shortest-path-to-a-point queries, which may be of independent interest: to report efficiently a shortest path from s to a query segment in the domain.

Wireless communication systems, such as RFIDs and wireless sensor networks, are increasingly being used in security-sensitive applications, e.g. credit card transactions or monitoring patient health in hospitals. Wireless jamming by transmitting artificial noise, which is traditionally used as an offensive technique for disrupting communication, has recently been explored as a means of protecting sensitive communication from eavesdroppers.

Security-sensitive applications, such as patient health monitoring and credit card transactions, are increasingly utilizing wireless communication systems, RFIDs, wireless sensor networks, and other wireless communication systems. The use of interference-emitting jammers to protect these sensitive communications has been recently explored in the literature, and has shown high potential. In this paper we consider optimization problems relating to the temporal distributions of jammers' activity, and the suitable coding regimes used for communication. Solving the joint problem optimally enables comprehensive security in space, at a low power consumption and low communication overhead. The joint optimization of jamming in space and time is driven by a new framework that uses the bit-error probability as a measure of communication quality. Under this framework, we show how to guarantee information-theoretic security within a geographic region, and with increased flexibility to tailor the coding regime to the problem's geometry. We present efficient algorithms for different settings, and provide simulations for various scenarios using the bit-error probability functions. These simulations demonstrate the efficiency of the scheme. We believe that our scheme can lead to practical, economical and scalable solutions for providing another layer of protection of sensitive data, in cases where encryption schemes are limited or impractical.

We study a facility location problem motivated by requirements pertaining to the distribution of charging stations for electric vehicles: Place a minimum number of battery charging stations at a subset of nodes of a network, so that battery-powered electric vehicles will be able to move between destinations using "t-spanning" routes, of lengths within a factor t > 1 of the length of a shortest path, while having sufficient charging stations along the way. We give constant-factor approximation algorithms for minimizing the number of charging stations, subject to the t-spanning constraint. We study two versions of the problem, one in which the stations are required to support a single ride (to a single destination), and one in which the stations are to support multiple rides through a sequence of destinations, where the destinations are revealed one at a time.

Homotopic routing asks for a path going around holes according to a given “threading”. Paths of different homo-topy types can be used to improve load balancing and routing resilience. We propose the first lightweight homotopic routing scheme that generates constant bounded stretch compared to the shortest path of the same homotopy type. Our main insight is that in a sequence of triangles to traverse, a message always routed to the nearest point on the next triangle in the sequence travels at most a constant times the length of any shortest path going through the same sequence of triangles. Our routing scheme operates on two levels enabled by a coarse triangulation. The top level is used to specify and represent the requested homotopy type, while the bottom level executes the local greedy routing on a triangle sequence. After a preprocessing step that triangulates the given region and creates a minimum-size auxiliary structure, routing operates greedily at two different resolutions. We also present simulation analysis in a variety of settings and show that the paths indeed have small stretch in practice, considerably shorter than the bounds guaranteed by the theory.

Given a connected polygonal domain P, the watchman route problem is to compute a shortest path or tour for a mobile guard (the “watchman”) that is required to see every point of P. While the watchman route problem is polynomially solvable in simple polygons, it is known to be NP-hard in polygons with holes.

We propose algorithms for computing optimal trajectories of a group of flying observers (such as helicopters or UAVs) searching for a lost child in a hilly terrain. Very few assumptions are made about the speed or direction of the child's motion and whether it might (either deliberately or accidentally) try to avoid being found. This framework can also be applied to seekers searching for hostile evaders, such as smugglers/criminals, or friendly evaders, such as lost hikers.

We explore the art gallery problem for the special case that the domain (gallery) P is an m-polyomino, a polyform whose cells are m unit squares. We study the combinatorics of guarding polyominoes in terms of the parameter m, in contrast with the traditional parameter n, the number of vertices of P; in particular, we show that floor((m+1)/3) point guards are always sufficient and sometimes necessary to cover an m-polyomino. When m d 3n/4 - 4, the point guard sufficiency condition yields a strictly lower guard number than floor(n/4), given by the art gallery theorem for orthogonal polygons. When pixels behave themselves like guards (pixel guards), we prove that floor(3m/11) + 1 guards are sufficient and sometimes necessary to cover an m-polyomino. We also study the algorithmic complexity of computing optimal guard sets for polyominoes. We prove that determining the guard number of a given m-polyomino is NP-hard. We provide polynomial-time algorithms to solve exactly some special cases in which the polyomino is "thin".

In the Euclidean TSP with neighborhoods (TSPN) problem we seek. shortest tour that visits a given set of n neighborhoods. The Euclidean TSPN generalizes the standard TSP on points.

Traditional algorithms in computational geometry assume that the input points are given precisely. In practice, data is usually imprecise, but information about the imprecision is often available. In this context, we investigate what the value of this information is. We show here how to preprocess a set of disjoint regions in the plane of total complexity n in $O(n\log n)$ time so that if one point per set is specified with precise coordinates, a triangulation of the points can be computed in linear time. In our solution, we solve another problem which we believe to be of independent interest. Given a triangulation with red and blue vertices, we show how to compute a triangulation of only the blue vertices in linear time.

The next generation of air transportation systems will have to use technology to be able to cope with the ever increasing demand for flights. Several challenging optimization problems arise in trying to maximize efficiency while maintaining safe operation in air traffic management (ATM). Constraints and issues unique to air transportation arise in the ATM domain, including weather hazards, turbulence, no-fly zones, and three-dimensional routing. The challenge is substantially compounded when the constraints vary in time and are not known with certainty, as is the case with weather hazards. Human oversight is provided by air traffic controllers, who are responsible for safe operation within a portion of airspace known as a sector. In this talk we discuss algorithmic methods that can be used in modeling and solving air traffic management problems, including routing of traffic flows, airspace configuration into load-balanced sectors, and capacity estimation in the face of dynamic and uncertain constraints and demands. We highlight several open problems.

We present a novel technique for reconstructing sharp features in surface models. The algorithm is designed to fit sharp features of low algebraic and combinatorial complexity in the gaps between smooth surface patches.

Localization is a fundamental problem in robotics. The “kidnapped robot” possesses a compass and map of its environment; it must determine its location at a minimum cost of travel distance. The problem is NP-hard [G. Dudek, K. Romanik, and S. Whitesides, SIAM J. Comput., 27 (1998), pp. 583–604] even to minimize within factor $c\log n$ [C. Tovey and S. Koenig, Proceedings of the National Conference on Artificial Intelligence, Austin, TX, 2000, pp. 819–824], where n is the map size. No approximation algorithm has been known. We give an $O(\log^3n)$-factor algorithm. The key idea is to plan travel in a “majority-rule” map, which eliminates uncertainty and permits a link to the $\frac{1}{2}$-Group Steiner (not Group Steiner) problem. The approximation factor is not far from optimal: we prove a $c\log^{2-\epsilon}n$ lower bound, assuming $NP\not\subseteq ZTIME(n^{polylog(n)})$, for the grid graphs commonly used in practice. We also extend the algorithm to polygonal maps by discretizing the problem using novel geometric techniques.

The National Airspace System (NAS) is designed to accommodate a large number of flights over North America. For purposes of workload limitations for air traffic controllers, the airspace is partitioned into approximately 600 sectors; each sector is observed by one or more controllers. In order to satisfy workload limitations for controllers, it is important that sectors be designed carefully according to the traffic patterns of flights, so that no sector becomes overloaded. We formulate and study the airspace sectorization problem from an algorithmic point of view, modeling the problem of optimal sectorization as a geometric partition problem with constraints. The novelty of the problem is that it partitions data consisting of trajectories of moving points, rather than static point set partitioning that is commonly studied. First, we formulate and solve the 1d version of the problem, showing how to partition a line into “sectors” (intervals) according to historical trajectory data. Then, we apply the 1D solution framework to design a 2D sectorization heuristic based on binary space partitions. We also devise partitions based on balanced “pie partitions” of a convex polygon. We evaluate our 2D algorithms experimentally. We conduct experiments using actual historical flight track data for the NAS as the basis of our partitioning. We compare the workload balance of our methods to that of the existing set of sectors for the NAS and find that our resectorization yields competitive and improved workload balancing. In particular, our methods yield an improvement by a factor between 2 and 3 over the current sectorization in terms of the time-average and the worst-case workloads of the maximum workload sector. An even better improvement is seen in the standard deviations (over all sectors) of both time-average and worst-case workloads.

We consider the problem of finding a maximum number of disjoint paths for unit disks moving amidst static or dynamic obstacles. For the static case we give efficient exact algorithms, based on adapting the "continuous uppermost path" paradigm. As a by-product, we establish a continuous analogue of Menger's Theorem. (In this extended abstract we only state these results.)

This video illustrates an algorithm for computing a maximum number of disjoint paths for unit disks moving among a set of dynamic obstacles in the plane. The problem is motivated by applications in air traffic management: aircraft must be routed while avoiding no-fly zones and weather constraints and while maintaining at least a specified horizontal separation distance between themselves. Given a polygonal domain with moving obstacles, our goal is to determine the maximum number of unit disks (aircraft with safety zones) that can be routed safely through the domain, entering/exiting through specified edges of the domain.

Abstract—We study the problem of data-driven routing and navigation in a distributed sensor network over a continuous scalar field. Specifically, we address the problem of searching for the collection of sensors with readings within a specified range. This is named the iso-contour query problem. We develop a gradient based routing scheme such that from any query node, the query message follows the signal field gradient or derived quantities and successfully discovers all iso-contours of interest. Due to the existence of local maxima and minima, the guaranteed delivery requires preprocessing of the signal field and the construction of a contour tree in a distributed fashion. Our approach has the following properties: (i) the gradient routing uses only local node information and its message complexity is close to optimal, as shown by simulations; (ii) the preprocessing message complexity is linear in the number of nodes and the storage requirement for each node is a small constant. The same preprocessing also facilitates route computation between any pair of nodes where the the route lies within any user supplied range of values. I.

We study the problem of contour tracking with binary sensors, an important problem for monitoring spatial signals and tracking group targets. In particular, we track the boundaries of the blobs of interest and capture the topological changes as the blobs merge or split. Only the nodes on the boundaries of these deformable blobs stay active and the repair cost is proportional to the size of the contour changes. Our algorithm is completely distributed, requires only local information, and yet captures the global topological properties. The algorithm performs a fundamental monitoring function and is a foundation for further information processing of spatial sensor data.

We investigate algorithmic questions that arise in the statistical problem of computing lines or hyperplanes of maximum regression depth among a set of n points. We work primarily with a dual representation and find points of maximum undirected depth in an arrangement of lines or hyperplanes. An O(n d ) time and O(n d−1) space algorithm computes undirected depth of all points in d dimensions. Properties of undirected depth lead to an O(nlog 2 n) time and O(n) space algorithm for computing a point of maximum depth in two dimensions, which has been improved to an O(nlog n) time algorithm by Langerman and Steiger (Discrete Comput. Geom. 30(2):299–309, [2003]). Furthermore, we describe the structure of depth in the plane and higher dimensions, leading to various other geometric and algorithmic results.

We propose heuristics for visibility coverage of a polygon with the fewest point guards. This optimal coverage problem, often called the “art gallery problem”, is known to be NP-hard, so most recent research has focused on heuristics and approximation methods. We evaluate our heuristics through experimentation, comparing the upper bounds on the optimal guard number given by our methods with computed lower bounds based on heuristics for placing a large number of visibility-independent “witness points”. We give experimental evidence that our heuristics perform well in practice, on a large suite of input data; often the heuristics give a provably optimal result, while in other cases there is only a small gap between the computed upper and lower bounds on the optimal guard number.

Article Share on Thick non-crossing paths and minimum-cost flows in polygonal domains Authors: Valentin Polishchuk Helsinki Institute for Information Technology, Helsinki, Finland Helsinki Institute for Information Technology, Helsinki, FinlandView Profile , Joseph S.B. Mitchell Stony Brook University, Stony Brook, NY Stony Brook University, Stony Brook, NYView Profile Authors Info & Claims SCG '07: Proceedings of the twenty-third annual symposium on Computational geometryJune 2007 Pages 56–65https://doi.org/10.1145/1247069.1247079Online:06 June 2007Publication History 17citation292DownloadsMetricsTotal Citations17Total Downloads292Last 12 Months6Last 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 the first constant‐factor approximation algorithm for a nontrivial instance of the optimal guarding (coverage) problem in polygons. In particular, we give an $O(1)$‐approximation algorithm for placing the fewest point guards on a 1.5D terrain, so that every point of the terrain is seen by at least one guard. While polylogarithmic‐factor approximations follow from set cover results, our new results exploit the geometric structure of terrains to obtain a substantially improved approximation algorithm.

We consider a class of geometric facility location problems in which the goal is to determine a set X of disks given by their centers (tj) and radii (rj) that cover a given set of demand points Y∈R2 at the smallest possible cost. We consider cost functions of the form Εjf(rj), where f(r)=rα is the cost of transmission to radius r. Special cases arise for α=1 (sum of radii) and α=2 (total area); power consumption models in wireless network design often use an exponent α>2. Different scenarios arise according to possible restrictions on the transmission centers tj, which may be constrained to belong to a given discrete set or to lie on a line, etc.We obtain several new results, including (a) exact and approximation algorithms for selecting transmission points tj on a given line in order to cover demand points Y∈R2; (b) approximation algorithms (and an algebraic intractability result) for selecting an optimal line on which to place transmission points to cover Y; (c) a proof of NP-hardness for a discrete set of transmission points in R2 and any fixed α>1; and (d) a polynomial-time approximation scheme for the problem of computing a minimum cost covering tour (MCCT), in which the total cost is a linear combination of the transmission cost for the set of disks and the length of a tour/path that connects the centers of the disks.

We study the problem of covering a set of points or polyhedra in R3 with two axis-aligned boxes in order to minimize a function of the measures of the two boxes, such as the sum or the maximum of their volumes. This 2-box cover problem arises naturally in the construction of bounding volume hierarchies, as well as in shape approximation and clustering. Existing algorithms solve the min-max version of the exact problem in quadratic time. Our results are more general, addressing min-max, min-sum and other versions. Our results give the first approximation schemes for the problem, which run in nearly linear time, as well as some new exact algorithms. We give (1+e)-approximation algorithms for minimizing the maximum or sum of volumes (or surface areas, diameters, widths, or girths) of the two boxes in R3. We investigate also the problem of computing balanced coverings, in which each box covers at least a fraction of the input objects, and we discuss the application to constructing provably-good bounding volume hierarchies of polyhedra. We also generalize our results to higher dimension.

We extend linkage unfolding results from the well-studied case of polygonal linkages to the more general case of linkages of polygons. More precisely, we consider chains of nonoverlapping rigid planar shapes (Jordan regions) that are hinged together sequentially at rotatable joints. Our goal is to characterize the familes of planar shapes that admit locked chains, where some configurations cannot be reached by continuous reconfiguration without self-intersection, and which families of planar shapes guarantee universal foldability, where every chain is guaranteed to have a connected configuration space. Previously, only obtuse triangles were known to admit locked shapes, and only line segments were known to guarantee universal foldability. We show that a surprisingly general family of planar shapes, called slender adornments, guarantees universal foldability: roughly, the inward normal from any point on the shape's boundary should intersect the line segment connecting the two incident hinges. In constrast, we show that isosceles triangles with any desired apex angle <90° admit locked chains, which is precisely the threshold beyond which the inward-normal property no longer holds.

This video illustrates the k-LinkSolver software for computing k-link shortest paths in weighted regions. The k-LinkSolver implements methods to find paths of length at most (1+e) times the length of a shortest k-link path, for any fixed e>0, and having at most 2k−1 links. The methods implemented are an improvement over the previously known (1+e)-approximation algorithms, which guarantee at most 5k−2 links.

Wireless sensor networks are tightly associated with the underlying environment in which the sensors are deployed. The global topology of the network is of great importance to both sensor network applications and the implementation of networking functionalities. In this paper we study the problem of topology discovery, in particular, identifying boundaries in a sensor network. Suppose a large number of sensor nodes are scattered in a geometric region, with nearby nodes communicating with each other directly. Our goal is to find the boundary nodes by using only connectivity information. We do not assume any knowledge of the node locations or inter-distances, nor do we enforce that the communication graph follows the unit disk graph model. We propose a simple, distributed algorithm that correctly detects nodes on the boundaries and connects them into meaningful boundary cycles. We obtain as a byproduct the medial axis of the sensor field, which has applications in creating virtual coordinates for routing. We show by extensive simulation that the algorithm gives good results even for networks with low density. We also prove rigorously the correctness of the algorithm for continuous geometric domains.

Localization is an important and extensively studied problem in ad-hoc wireless sensor networks. Given the connectivity graph of the sensor nodes,along with additional local information (e.g. distances, angles, orientations etc.), the goal is to reconstruct the global geometry of the network. In this paper, we study the problem of localization with noisy distance and angle information. With no noise at all, the localization problem with both angle (with orientation) and distance information is trivial. However, in the presence of even a small amount of noise, we prove that the localization problem is NP hard.Localization with accurate distance information and relative angle information is also hard. These hardness results motivate our study of approximation schemes. We relax the non-convex constraints to approximating convex constraints and propose linear programs (LP) for two formulations of the resulting localization problem, which we call the weak deployment and strong deployment problems.These two formulations give upper and lower bounds on the location uncertainty respectively: No sensor is located outside its weak deployment region, and each sensor can be anywhere in its strong deployment region without violating the approximate distance and angle constraints. Though LP-based algorithms are usually solved by centralized methods, we propose distributed, iterative methods, which are provably convergent to the centralized algorithm solutions. We give simulation results for the distributed algorithms, evaluating the convergence rate, dependence on measurement noises,and robustness to link dynamics.

This paper study two problems that arise in optimization of sensor networks: First, we devise provable approximation schemes for locating a base station and constructing a network among a set of sensors each of which has a data stream to get to the base station. Subject to power constraints at the sensors, our goal is to locate the base station and establish a network in order to maximize the lifespan of the network. Second, we study optimal sensor placement problems for quality coverage of given domains cluttered with obstacles. We assume "line-of-site", sensors, that sense a point only if the straight segment connecting the sensor to this point (the "line-of-site") does not cross any obstacle. so obstacles occludes area from using line-of-site sensors, the goal is to minimize the number of sensors required in order to have each point "well covered" according to precise criteria (e.g., that each point is seen by two sensors that form at least angle a, or that each point is seen by three sensors that form a triangle containing the point).

We give the first algorithmic study of a class of "covering tour" problems related to the geometric traveling salesman problem: Find a polygonal tour for a cutter so that it sweeps out a specified region ("pocket") in order to minimize a cost that depends mainly on the number of turns. These problems arise naturally in manufacturing applications of computational geometry to automatic tool path generation and automatic inspection systems, as well as arc routing ("postman") problems with turn penalties. We prove the NP-completeness of minimum-turn milling and give efficient approximation algorithms for several natural versions of the problem, including a polynomial-time approximation scheme based on a novel adaptation of the m-guillotine method.

We study the problem of computing the visibility graph defined by a set P of n points inside a polygon Q: two points p,q ε P are joined by an edge if the segment ‾pq ⊂ Q. Efficient output-sensitive algorithms are known for the case in which P is the set of all vertices of Q. We examine the general case in which P is an arbitrary set of points, interior or on the boundary of Q and study a variety of algorithmic questions. We give an output-sensitive algorithm, which is nearly optimal, when Q is a simple polygon. We introduce a notion of "fat" or "robust" visibility, and give a nearly optimal algorithm for computing visibility graphs according to it, in polygons Q that may have holes. Other results include an algorithm to detect if there are any visible pairs among P, and algorithms for output-sensitive computation of visibility graphs with distance restrictions, invisibility graphs, and rectangle visibility graphs.

We revisit the problem of computing shortest obstacle-avoiding paths among obstacles in three dimensions. We prove new hardness results, showing, e.g., that computing Euclidean shortest paths among sets of "stacked" axis-aligned rectangles is NP-complete, and that computing L1-shortest paths among disjoint balls is NP-complete. On the positive side, we present an efficient algorithm for computing an L1-shortest path between two given points that lies on or above a given polyhedral terrain. We also give polynomial-time algorithms for some versions of stacked polygonal obstacles that are "terrain-like" and analyze the complexity of shortest path maps in the presence of parallel halfplane "walls.

In the "freeze-tag" problem, we are given a swarm of n sleeping (frozen or inactive) robots and a single awake (active) robot. The goal is to awaken all robots in the shortest possible time. A robot is awakened when an active robot "touches" it. The goal is to compute an optimal awakening schedule such that all robots are awake by time t/sup */, for the smallest possible value of t/sup */. We devise and test a variety of heuristic strategies on geometric and network datasets. Our experiments show that all of the strategies perform acceptably well, with the simple greedy strategy performing particularly well. A theoretical analysis of the greedy strategy gives a tight approximation bound of /spl Theta/(/spl radic/logn) for points in the plane. We show more generally a tight performance bound of /spl Theta/((logn)/sup 1-1/d/) in d dimensions. The geometric case contrasts with the case of general metric spaces, where greedy is known to have a /spl Theta/(logn) approximation factor, and no method is known to achieve an approximation factor of o(logn).

No abstract available.

Given a sequence of k polygons in the plane, a start point s, and a target point, t, we seek a shortest path that starts at s, visits in order each of the polygons, and ends at t. If the polygons are disjoint and convex, we give an algorithm running in time O(kn log (n/k)), where n is the total number of vertices specifying the polygons. We also extend our results to a case in which the convex polygons are arbitrarily intersecting and the subpath between any two consecutive polygons is constrained to lie within a simply connected region; the algorithm uses O(nk2 log n) time. Our methods are simple and allow shortest path queries from s to a query point t to be answered in time O(k log n + m), where m is the combinatorial path length. We show that for nonconvex polygons this "touring polygons" problem is NP-hard.The touring polygons problem is a strict generalization of some classic problems in computational geometry, including the safari problem, the zoo-keeper problem, and the watchman route problem in a simple polygon. Our new results give an order of magnitude improvement in the running times of the safari problem and the watchman route problem: We solve the safari problem in O(n2 log n) time and the watchman route problem (through a fixed point s) in time O(n3 log n), compared with the previous time bounds of O(n3) and O(n4), respectively.

The Computational Plant or Cplant is a commodity-based supercomputer under development at Sandia National Laboratories. This paper describes resource-allocation strategies to achieve processor locality for parallel jobs in Cplant and other supercomputers. Users of Cplant and other Sandia supercomputers submit parallel jobs to a job queue. When a job is scheduled to run, it is assigned to a set of processors. To obtain maximum throughput, jobs should be allocated to localized clusters of processors to minimize communication costs and to avoid bandwidth contention caused by overlapping jobs. This paper introduces new allocation strategies and performance metrics based on space-filling curves and one dimensional allocation strategies. These algorithms are general and simple. Preliminary simulations and Cplant experiments indicate that both space-filling curves and one-dimensional packing improve processor locality compared to the sorted free list strategy previously used on Cplant. These new allocation strategies are implemented in the new release of the Cplant System Software, Version 2.0, phased into the Cplant systems at Sandia by May 2002.

The terrain surface simplification problem has been studied extensively, as it has important applications in geographic information systems and computer graphics. The goal is to obtain a new surface that is combinatorially as simple as possible, while maintaining a prescribed degree of similarity with the original input surface. Generally, the approximation error is measured with respect to distance (e.g., Hausdorff) from the original or with respect to visual similarity. In this paper, we propose a new method of simplifying terrain surfaces, designed specifically to maximize a new measure of quality based on preserving inter-point visibility relationships. Our work is motivated by various problems of terrain analysis that rely on inter-point visibility relationships, such as optimal antenna placement.We have implemented our new method and give experimental evidence of its effectiveness in simplifying terrains according to our quality measure. We experimentally compare its performance with that of other leading simplification methods.

Motivated by applications in computer graphics, we study the problem of computing an optimal encoding in "triangle strips" of a triangulation of a polygonal surface model. The goal is to facilitate the transmission and rendering of a polygonal model by decomposing its triangulation into a minimum number of "tristrips," each of which has its connectivity stored implicitly in the ordering of the data points. While this optimization problem has been conjectured to be hard, its complexity status has been open. We prove that the tristrip decomposition problem is, in fact, NP-complete. We also propose two methods for solving the problem to optimality, one based on an integer programming formulation, one based on a branch-and-bound scheme that relies on lower bounding techniques for its efficiency. We perform an extensive set of experiments to test the efficiencies of these methods and some of their variants. These methods have been integrated also with the practical system FTSG (Fast Triangle Strip Generator), in order to utilize optimization methods on small subproblems to improve the quality of the heuristic solutions obtained by FTSG. We use experimentation to judge the quality of the improvements.

We study several natural proximity and facility location problems that arise for a set ${\cal P}$ of $n$ points and a set $\R$ of $m$ disjoint rectangular obstacles in the plane, where distances are measured according to the $L_1$ shortest path (geodesic) metric. In particular, we compute, in time $O(mn\log(m+n))$, a data structure of size $O(mn)$ that supports $O(\log(m+n))$-time farthest point queries; we avoid computing the more complicated farthest neighbor Voronoi diagram, whose combinatorial complexity we show to be $\Theta(mn)$. We study the center point problem, finding in $O(mn\log(m+n))$ time a center point (and the set of center points) that minimize the maximum distance to sites of ${\cal P}$; this result improves the best previous bound by a factor of roughly $m$. In addition, we give algorithms for approximating the diameter, $D$, and radius, $r$, of ${\cal P}$, including methods to (i) compute a pair of points $a,b \in {\cal P}$, such that $d(a,b) \ge (1-\eps)D$, in $O(n\log n + \frac{1}{\eps}(n+m) \log m)$ time; and (ii) compute a point $c'$, such that $\max \{d(p, c') \ | \ p \in {\cal P}\} \le (1+\eps)r$, in $O(n\log(m+n) + (m/\eps)\log(m+1/\eps))$ time. Finally, we show that for all the problems above it is enough to consider only a subset of ${\cal P}$. This subset is likely to be much smaller than ${\cal P}$, it is computable in $O(n \log n)$ time, and using it results in significantly decreased runtime in practice.

We provide a variety of new results, including upper and lower bounds, as well as simpler proof techniques for the efficient construction of binary space partitions (BSP's) of axis-parallel segments, rectangles, and hyperrectangles. (a) A consequence of the analysis in \cite{dAF} is that any set of $n$ axis-parallel and pairwise-disjoint line segments in the plane admits a binary space partition of size at most $2n-1$. We establish a worst-case lower bound of $2n-o(n)$ for the size of such a BSP, thus showing that this bound is almost tight in the worst case. (b) We give an improved worst-case lower bound of $\frac{9}{4}n-o(n)$ on the size of a BSP for isothetic pairwise disjoint rectangles. (c) We present simple methods, with equally simple analysis, for constructing BSP's for axis-parallel segments in higher dimensions, simplifying the technique of \cite{PY2} and improving the constants. (d) We obtain an alternative construction (to that in \cite{PY2}) of BSP's for collections of axis-parallel rectangles in 3-space. (e) We present a construction of BSP's of size $O(n^{5/3})$ for $n$ axis-parallel pairwise disjoint 2-rectangles in $\reals^4$, and give a matching worst-case lower bound of $\Omega(n^{5/3})$ for the size of such a BSP. (f) We extend the results of \cite{PY2} to axis-parallel $k$-dimensional rectangles in $\reals^d$, for $k

We study the problem of simplifying a polygonal subdivision, subject to a given error bound, , and subject to maintaining the topology of the input, while not introducing new (Steiner) vertices. In particular, we require that the simpli- ed chains may not cross themselves or cross other chains. In GIS applications, for example, we are interested in simplifying the banks of a river without the left and right banks getting \\tangled" and without \\islands" becoming part of the land mass. Maintaining topology during subdivision simplication is an important constraint in many real GIS applications. We give both theoretical and experimental results. (a). We prove that the general problem we are trying to solve is in fact dicult to solve, even approximately: we show that it is MIN PB-complete and that, in particular, assuming P 6= NP, in the general case we cannot obtain in polynomial time an approximation within a factor n 1=5 of an optimal solution. (b). We propose some heuristic methods for solving the problem, which we have implemented. Our experimental results show that, in practice, we get quite good simplications in a reasonable amount of time. Keywords polygonal subdivisions, simplication, map generalization, geographic information systems, approximation algorithms 1.

We give the first exact algorithmic study of facility location problems that deal with finding a median for a continuum of demand points.In particular, we consider versions of the "continuous k-median (Weber) problem" where the goal is to select one or more center points that minimize the average distance to a set of points in a demand region.In such problems, the average is computed as an integral over the relevant region, versus the usual discrete sum of distances.The resulting facility location problems are inherently geometric, requiring analysis techniques of computational geometry.We provide polynomial-time algorithms for various versions of the L1 1-median (Weber) problem.We also consider the multiple-center version of the L1 k-median problem, which we prove is NP-hard for large k.

We show a remarkable fact about folding paper: From a single square of paper, one can fold it into a flat origami that takes the (scaled) shape of any connected polygonal region, even if it has holes.This resolves a longstanding open problem in origami design.Our proof is constructive, utilizing tools of computational geometry, resulting in efficient algorithms for achieving the target silhouette.We show further that if the paper has a different color on each side, we can form any connected polygonal pattern of two colors.Our results apply also to polyhedral surfaces, showing that any polyhedron can be "wrapped" by folding a strip of paper around it.We give three methods for solving these problems: the first uses a thin strip whose area is arbitrarily close to optimal; the second allows wider strips to be used; and the third varies the strip width to make a folding that optimizes the number or length of visible "seams."

We investigate algorithmic questions that arise in the statistical problem of computing lines or hyperplanes of maximum regression depth among a set of n points.We work primarily with a dual representation and find points of maximum undirected depth in an arrangement of lines or hyperplanes.An O(nd) time and space algorithm computes directed depth of all points in d dimensions.Properties of undirected depth lead to an O(n log2 n) time and O(n) space algorithm for computing a point of maximum depth in two dimensions.We also give approximation algorithms for hyperplane arrangements and degenerate line arrangements.

We prove that the maximum number of geometric permutations, induced by line transversals to a collection of n pairwise disjoint balls in IRd, is O(nd-l).This improves substantially the upper bound of O(n2d-2) known for general convex sets [9].We show that the maximum number of geometric permutations of a sufficiently large collection of pairwise disjoint unit discs in the plane is 2, improving the previous upper bound of 3 given in [5].

A fundamental algorithmic problem in computer graphics is that of computing a succinct encoding of a triangulation of a polygonal surface model in order to be able to transmit and render it efficiently.The goal is to take a given polygonal surface model, whose facets are given by (possibly multiply-connected) polygons, triangulate its facets, and then decompose the triangulation into a small number of "tristrips," each of which has its connectivity stored implicitly in the ordering of the data points.We develop methods that are effective in solving the stripification problem, both in theory (provably good encodings) and in practice.Our methods are based on carefully constructed search trees in the dual graph, followed by algorithms to decompose dual trees into tristips.One decomposition algorithm is provably optimal (based on dynamic programming), allowing us a sound basis of comparison among our other (heuristic) algorithms.We demonstrate the speed and effectiveness of our algorithms through a battery of experiments.In comparison with the recently released STRIPE system for stripification, we find that our stripifier, FTSG, produces comparable or better quality encodings, while requiring significantly less computing time on a large variety of datasets.Further, FTSG is carefully engineered and implemented to be robust, even in the face of highly degenerate and corrupted real-world data.

Direct volume rendering based on projective methods works by projecting, in visibility order, the polyhedral cells of a mesh onto the image plane, and incrementally compositing the cell’s color and opacity into the final image. Crucial to this method is the computation of a visibility ordering of the cells. If the mesh is “well‐behaved” (acyclic and convex), then the MPVO method of Williams provides a very fast sorting algorithm; however, this method only computes an approximate ordering in general datasets, resulting in visual artifacts when rendered. A recent method of Silva et al. removed the assumption that the mesh is convex, by means of a sweep algorithm used in conjunction with the MPVO method; their algorithm is substantially faster than previous exact methods for general meshes. In this paper we propose a new technique, which we call BSP‐XMPVO, which is based on a fast and simple way of using binary space partitions on the boundary elements of the mesh to augment the ordering produced by MPVO. Our results are shown to be orders of magnitude better than previous exact methods of sorting cells.

We present techniques for matching point-sets in two and three dimensions under rigid-body transformations. We prove bounds on the worst-case performance of these algorithms to be within a small constant factor of optimal and conduct experiments to show that the average performance of these matching algorithms is often better than that predicted by the worst-case bounds.

We study the problem of computing a Hamiltonian tour (cycle) or path on a set of points in order to maximize the minimum edge length in the tour or path. This "maximum scatter" traveling salesperson problem (TSP) is closely related to the bottleneck TSP and is motivated by applications in manufacturing (e.g., sequencing of rivet operations) and medical imaging. In this paper, we give the first algorithmic study of these problems, including complexity results, approximation algorithms, and exact algorithms for special cases. In an attempt to model more accurately the real problems that arise in practice, we also generalize the basic problem to consider a more general measure of "scatter" in which points on a tour or path should be far not only from their immediate predecessor and successor, but also from other near-neighbors along the tour or path.

We show that any polygonal subdivision in the plane can be converted into an "m-guillotine" subdivision whose length is at most $(1+{c\over m})$ times that of the original subdivision, for a small constant c. "m-Guillotine" subdivisions have a simple recursive structure that allows one to search for the shortest of such subdivisions in polynomial time, using dynamic programming. In particular, a consequence of our main theorem is a simple polynomial-time approximation scheme for geometric instances of several network optimization problems, including the Steiner minimum spanning tree, the traveling salesperson problem (TSP), and the k-MST problem.

WC study a variety of geometric network optimization prob lcms on a set of points, in which we are given a resource bound, a, on the total length of the network, and our ob jcctivc is to maximize the number of points visited (or the total "value" of points visited), In particular, we resolve the well-publicized open problem on the approximabiity of the rooted "orienteering problem" for the case in which the sites are given as points in the plane and the network required is a cycle.We obtain a 2approximation for this problem, We also obtain approximation algorithms for variants of this problem in which the network required is a tree (S-approximation) or a path Q-approximation).No prior approximation bounds were known for any of these problems,We also obtain improved approximation algorithms for geometric instances of the unrooted orienteering problem, where we obtain a 2-approximation for both the cycle and tree versions of the problem on points in the plane, as well as a G-approximation for the tree version in edge-weighted graphs, E'urther, we study generalizations of the basic orienteering problem, to the case of multiple roots, sites that are polygonnl regions, etc., where we again give the first known approximation results.Our methods are based on some new tools which may be of interest in their own right: ( 1) some new results on m-'Department of Applied Mathematics and Statistics, State Univcrsitv of New York.Stonv Brook.NY 11794-3600: aat~o6smb .ounyob.

We show that any rectilinear polygonal subdivision in the plane can be converted into a "guillotine" subdivision whose length is at most twice that of the original subdivision. "Guillotine" subdivisions have a simple recursive structure that allows one to search for "optimal" such subdivisions in polynomial time, using dynamic programming. In particular, a consequence of our main theorem is a very simple proof that the k-MST problem in the plane has a constant-factor polynomial-time approximation algorithm: we obtain a factor of 2 (resp., 3) for the L 1 metric, and a factor of $2\sqrt{2}$ (resp., 3.266) for the L 2 (Euclidean) metric in the case in which Steiner points are allowed (resp., not allowed).

Collision detection is of paramount importance for many applications in computer graphics and visualization. Typically, the input to a collision detection algorithm is a large number of geometric objects comprising an environment, together with a set of objects moving within the environment. In addition to determining accurately the contacts that occur between pairs of objects, one needs also to do so at real-time rates. Applications such as haptic force feedback can require over 1000 collision queries per second. We develop and analyze a method, based on bounding-volume hierarchies, for efficient collision detection for objects moving within highly complex environments. Our choice of bounding volume is to use a discrete orientation polytope (k-DOP), a convex polytope whose facets are determined by halfspaces whose outward normals come from a small fixed set of k orientations. We compare a variety of methods for constructing hierarchies (BV-trees) of bounding k-DOPs. Further, we propose algorithms for maintaining an effective BV-tree of k-DOPs for moving objects, as they rotate, and for performing fast collision detection using BV-trees of the moving objects and of the environment. Our algorithms have been implemented and tested. We provide experimental evidence showing that our approach yields substantially faster collision detection than previous methods.

We present a practical new algorithm for the problem of computing low-cost paths in a weighted planar subdivision or on a weighted polyhedral surface.The algorithm is baaed on constructing a relatively sparse graph, a "pathnet", that links selected pairs of subdivision vertices (and "critical points of entry") with locally optimal paths.The pathnet can be searched for pat hs that are provably close to optimal and approach optimal, as one varies the parameter that controls the sparsity of the pathnet.We analyze our algorithm both analytically and experimentally.We report on the results of a set of experiments comparing the new algorithm with other standard methods.The weighted region problem models the minimum-time path problem for a point robot moving in a terrain of varied

A fundamental problem in computer vision is identifying which of a given set of geometric models is present in animage.Reconsider anapproach to model recognition basedon computing efficient strategies (decision trees) for 'probing" a scanned image of a typeset document, in order to perform fast and effective optical character recognition (OCR).We consider a "proben to be a simply computed local operator that can be applied to discriminate between two sets of possible models.By carefully constructing effective probes, and assembling them into a geometric decision tree, we have devised, implemented, and compared a variety of methods to perform OCR.In this paper, we present algorithms for probing strategies and decision tree construction, and we report experiment al results on the effectiveness of theae algorithms in identifying English characters and numerals in scanned images of printed pages of text.These algorithms are implemented as part of a system used by a document processing company (Syngen Corp.).

We consider the problem of verifying a simple polygon in the plane using “test points”. A test point is a geometric probe that takes as input a point in Euclidean space, and returns “+” if the point is inside the object being probed or “−” if it is outside. A verification procedure takes as input a description of a target object, including its location and orientation, and it produces a set of test points that are used to verify whether a test object matches the description. We give a procedure for verifying an n-sided, non-degenerate, simple target polygon using 5n test points. This testing strategy works even if the test polygon has n + 1 vertices, and we show a lower bound of 3n + 1 test points for this case. We also give algorithms using O(n) test points for simple polygons that may be degenerate and for test polygons that may have up to n + 2 vertices. All of these algorithms work for polygons with holes. We also discuss extensions of our results to higher dimensions.

Lazy sweep ray casting is a fast algorithm for rendering general irregular grids. It is based on the sweep-plane paradigm, and it is able to accelerate ray casting for rendering irregular grids, including disconnected and nonconvex unstructured irregular grids (even with holes) with a rendering cost that decreases as the "disconnectedness" decreases. The algorithm is carefully tailored to exploit spatial coherence even if the image resolution differs substantially from the object space resolution. Lazy sweep ray casting has several desirable properties, including its generality, (depth-sorting) accuracy, low memory consumption, speed, simplicity of implementation and portability (e.g. no hardware dependencies). We establish the practicality of our method through experimental results based on our implementation, which is shown to be substantially faster (by up to two orders of magnitude) than other algorithms implemented in software. We also provide theoretical results, both lower and upper bounds, on the complexity of ray casting of irregular grids.

No abstract available.

Abstract We introduce the boxtree, a versatile data structure for representing triangulated or meshed surfaces in 3D. A boxtree is a hierarchical structure of nested boxes that supports efficient ray tracing and collision detection. It is simple and robust, and requires minimal space. In situations where storage is at a premium, boxtrees are effective alternatives to octrees and BSP trees. They are also more flexible and efficient than R‐trees, and nearly as simple to implement.

RouteProblem:Let P be a polygonal room, possibly with "holes" (obstacles), having n vertices.The problem of computing a shortest tour in order that a mobile guard can "see" all of T is known as the Watchman Route Problem (WRP).If P is a simple polygon (having no holes), then WRP can be solved exactly, in time 0(n4) [7, 23].However, WRP is known to be NP-hard if ~has holes (a simple reduction from Euclidean TSP; see [8]), even if T is rectilinear.But, as with RBSP, no approximation algorithms have previously been found for this problem.We give an O(log m) approximation algorithm for the WRP when the polygon T is rectilinear, where m < n is the minimum number of edges in a shortest rectilinear watchman route.

Proposes a new approach to the automatic generation of triangular irregular networks (TINs) from dense terrain models. We have developed and implemented an algorithm based on the greedy principle used to compute minimum-link paths in polygons. Our algorithm works by taking greedy cuts ("bites") out of a simple closed polygon that bounds the yet-to-be triangulated region. The algorithm starts with a large polygon, bounding the whole extent of the terrain to be triangulated, and works its way inward, performing at each step one of three basic operations: ear cutting, greedy biting, and edge splitting. We give experimental evidence that our method is competitive with current algorithms and has the potential to be faster and to generate many fewer triangles. Also, it is able to keep the structural terrain fidelity at almost no extra cost in running time and it requires very little memory beyond that for the input height array.

The authors give an algorithm to compute the visibility polygon from a point among a set of h pairwise-disjoint polygonal obstacles with a total of n vertices. The algorithm uses $O(n)$ space and runs in optimal time $\Theta (n + h \log h)$, improving the previous upper bound of $O(n \log n)$. A direct consequence of the algorithm is an $O(n + h \log h)$ time algorithm for computing the convex hull of h disjoint simple polygons.

We present practical methods for approximate geometric pattern matching in d-dimensions along with experimental data regarding the quality of matches and running times of these methods versus those of a branch-and-bound search. Our methods are faster than previous methods but still produce good matches.

Ray (segment) shooting is the problem of determining the first intersection between a ray (directed line segment) and a collection of polygonal or polyhedral obstacles. In order to process queries efficiently, the set of obstacle polyhedra is usually preprocessed into a data structure. In this paper we propose a query-sensitive data structure for ray shooting, which means that the performance of our data structure depends on the local geometry of obstacles near the query segment. We measure the complexity of the local geometry near the segment by a parameter called the simple cover complexity, denoted by scc(s) for a segment s. Our data structure consists of a subdivision that partitions the space into a collection of polyhedral cells, each of O(1) complexity. We answer a segment shooting query by walking along the segment through the subdivision. Our first result is that, for any fixed dimension d, there exists a simple hierarchical subdivision in which no query segment s intersects more than O(scc(s)) cells. Our second result shows that in two dimensions such a subdivision of size O(n) can be constructed in time O(n log n), where n is the total number of vertices in all the obstacles.

A fundamental problem in model-based computer vision is that of identifying which of a given set of geometric models is present in an image. Considering a “probe” to be an oracle that tells us whether or not a model is present at a given point, we study the problem of computing efficient strategies (“decision trees”) for probing an image, with the goal to minimize the number of probes necessary (in the worst case) to determine which single model is present. We show that a ⌈lg k ⌉ height binary decision tree always exists for k polygonal models (in fixed position), provided (1) they are non-degenerate (do not share boundaries) and (2) they share a common point of intersection. Further, we give an efficient algorithm for constructing such decision trees when the models are given as a set of polygons in the plane. We show that constructing a minimum height tree is NP-complete if either of the two assumptions is omitted. We provide an efficient greedy heuristic strategy and show that, in the general case, it yields a decision tree whose height is at most ⌈lg n ⌉ times that of an optimal tree. Finally, we discuss some restricted cases whose special structure allows for improved results.

We give a subquadratic (O(n5/3+e) time and space) algorithm for computing Euclidean shortest paths in the plane in the presence of polygonal obstacles; previous time bounds were at least quadratic in n, in the worst-case. The method avoids use of visibility graphs, relying instead on the continuous Dijkstra paradigm. The output is a shortest path map (of size O(n)) with respect to a given source point, which allows shortest path length queries to be answered in time O(log n). The algorithm extends to the case of multiple source points, yielding a geodesic Voronoi diagram within the same time bound.

The authors consider the problem of finding a shortest polygonal path from s to t within a simple polygon P, subject to the restriction that the path have at most k links (edges). They give an algorithm to compute a k-link path with length at most (1 + epsilon ) times the length of a shortest k-link path, for any error tolerance epsilon >0. The algorithm runs in time O(n/sup 3/k/sup 3/ log (Hk/ epsilon /sup 1/k/)), where N is the largest integer coordinate among the n vertices of P. They also study the more general problem of approximating shortest k-link paths in polygons with holes. In this case, they give an algorithm that returns a path with at most 2k links and length at most that of a shortest k-link path; the running time is O(kE/sup 2/), where E is the number of edges in the visibility graph. Finally, they study the bicriteria path problem in which the two criteria are link length and 'total turn' (the integral of mod Delta theta mod along a path). They obtain in an exact polynomial-time algorithm for polygons with holes.>

We consider several cases of the point matching problem in which we are to find a transformation of a set of n points such that each transformed point lies in one of n given pairwise-disjoint “noise regions.” We prove upper and lower bounds on the number of possible matches, under a variety of types of transformations (rotations, translations, similarity) and noise regions (circles, squares, polygons). We also give efficient algorithms for computing the set of all possible matches, along with a corresponding transformation that realizes each match. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

Article Arrangements of segments that share endpoints: single face results Share on Authors: Esther M. Arkin School of Operations Research and Industrial Engineering, Cornell University, Ithaca, NY School of Operations Research and Industrial Engineering, Cornell University, Ithaca, NYView Profile , Dan Halperin Department of Computer Science, School of Mathematical Sciences, Tel Aviv University Department of Computer Science, School of Mathematical Sciences, Tel Aviv UniversityView Profile , Klara Kedem Department of Computer Science, School of Mathematical Sciences, Tel Aviv University Department of Computer Science, School of Mathematical Sciences, Tel Aviv UniversityView Profile , Joseph S. B. Mitchell School of Operations Research and Industrial Engineering, Cornell University, Ithaca, NY School of Operations Research and Industrial Engineering, Cornell University, Ithaca, NYView Profile , Nir Naor Department of Computer Science, School of Mathematical Sciences, Tel Aviv University Department of Computer Science, School of Mathematical Sciences, Tel Aviv UniversityView Profile Authors Info & Claims SCG '91: Proceedings of the seventh annual symposium on Computational geometryJune 1991 Pages 324–333https://doi.org/10.1145/109648.109684Online:01 June 1991Publication History 1citation220DownloadsMetricsTotal Citations1Total Downloads220Last 12 Months3Last 6 weeks0 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

The problem of determining shortest paths through a weighted planar polygonal subdivision with n vertices is considered. Distances are measured according to a weighted Euclidean metric: The length of a path is defined to be the weighted sum of (Euclidean) lengths of the subpaths within each region. An algorithm that constructs a (restricted) “shortest path map” with respect to a given source point is presented. The output is a partitioning of each edge of the subdivion into intervals of ε-optimality, allowing an ε-optimal path to be traced from the source to any query point along any edge. The algorithm runs in worst-case time O ( ES ) and requires O ( E ) space, where E is the number of “events” in our algorithm and S is the time it takes to run a numerical search procedure. In the worst case, E is bounded above by O ( n 4 ) (and we give an Ω( n 4 ) lower bound), but it is likeky that E will be much smaller in practice. We also show that S is bounded by O ( n 4 L ), where L is the precision of the problem instance (including the number of bits in the user-specified tolerance ε). Again, the value of S should be smaller in practice. The algorithm applies the “continuous Dijkstra” paradigm and exploits the fact that shortest paths obey Snell's Law of Refraction at region boundaries, a local optimaly property of shortest paths that is well known from the analogous optics model. The algorithm generalizes to the multi-source case to compute Voronoi diagrams.

A method for comparing polygons that is a metric, invariant under translation, rotation, and change of scale, reasonably easy to compute, and intuitive is presented. The method is based on the L/sub 2/ distance between the turning functions of the two polygons. It works for both convex and nonconvex polygons and runs in time O(mn log mn), where m is the number of vertices in one polygon and n is the number of vertices in the other. Some examples showing that the method produces answers that are intuitively reasonable are presented.>

A number of problems in computational geometry involving simple polygons can be solved in linear time once the polygon has been triangulated. Since the worst-case time bound for triangulating a general simple polygon is currently super-linear, these algorithms are not linear time in the worst case. In this paper we define the structured visibility profile of a polygonal path and show how to compute it in linear time. We apply this result to solve many problems in linear time that previously required triangulation. Our list of problems includes: translation separability of two simple polygons, computing the weak visibility region for a segment within a simple polygon, finding shortest monotone paths in a simple polygon, ray shooting from an edge, and the convex rope problem.

Given a set of nonintersecting polygonal obstacles in the plane, the link distance between two points s and t is the minimum number of edges required to form a polygonal path connecting s to t that avoids all obstacles. We present an algorithm that computes the link distance (and a corresponding minimum-link path) between two points in time Ο(Eα(n) log2 n) (and space Ο(E)), where n is the total number of edges of the obstacles, E is the size of the visibility graph, and α(n) denotes the extremely slowly growing inverse of Ackermann's function.

We consider the terrain navigation problem in a two-dimensional polygonal subdivision with three types of regions: obstacles, “free” regions (in which one can travel at no cost), and regions in which cost is proportional to distance traveled. We present an algorithm whose running time is O(E + nlog n), where n is the number of vertices representing the subdivision, and E is bounded above by the size of the visibility graph induced by the set of obstacles and free regions, which is no worse than quadratic (O(n2)). In addition, we present algorithms to solve a variety of important generalizations and applications: (1) an O(n2) algorithm for constructing a critical graph of size O(n2) (which can be searched in time O(n2log n) for shortest paths) for the case in which linear features (roads) are added, thereby allowing arbitrary weights on the edges of the subdivision; (2) similar time bounds for the case in which the linear features include a possible “cost of crossing”; (3) an O(n2W) algorithm for finding lexicographically shortest paths in weighted regions (with W different weights); (4) an O(k2n2) algorithm for planning least-risk paths in a simple polygon that contains k line-of-sight threats (this becomes O(k4n4) in polygons with holes); and (5) an O(k2n3) algorithm for finding least-risk watchman routes in simple rectilinear polygons (a watchman route is such that each point in the polygon is visible from at least one point along the route). INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

We consider the following problem: given a set S of n points in the plane, we would like to compute for each point pϵS, how many triangles with corners at points in set S contain p. We give an O(n2) algorithm to solve the problem.

We introduce a new class of problems concerned with the computation of maximum flows through two-dimensional polyhedral domains. Given a polyhedral space (e.g., a simple polygon with holes), we want to find the maximum “flow” from a source edge to a sink edge. Flow is defined to be a divergence-free vector field on the interior of the domain, and capacity constraints are specified by giving the maximum magnitude of the flow vector at any point. The problem is the natural extension to the continuous domain of the discrete problem of finding maximum flows through a capacitated network. For this problem, Strang proved that max flow equals min cut; we address the problem of constructing min cuts and max flows. We give polynomial-time algorithms for maximum flow from a source edge to a sink edge through a simple polygon with uniform capacity constraint (with or without holes), maximum flow through a simple polygon from many sources to many sinks, and maximum flow through weighted polygonal regions. Central to our methodology is the intimate connection between the max-flow problem and its dual, the min-cut problem. We show how the continuous Dijkstra paradigm of solving shortest paths problems corresponds to a continuous version of the uppermost path algorithm for computation of maximum flow in a planar network.

We study the class of problems associated with the detection and computation of monotone paths among a set of disjoint obstacles. We give an Ο(nE) algorithm for finding a monotone path (if one exists) between two points in the plane in the presence of polygonal obstacles. (Here, E is the size of the visibility graph defined by the n vertices of the obstacles.) If all of the obstacles are convex, we prove that there always exists a monotone path between any two points s and t. We give an Ο(n log n) algorithm for finding such a path for any s and t, after an initial Ο(E + n log n) preprocesing. We introduce the notions of “monotone path map”, and “shortest monotone path map” and give algorithms to compute them. We apply our results to a class of separation and assembly problems, yielding polynomial-time algorithms for planning an assembly sequence (based on separations by single translations) of arbitrary polygonal parts in two dimensions.

We consider the terrain navigation problem in a two-dimensional polygonal subdivision consisting of obstacles, “free” regions (in which one can travel at no cost), and regions in which cost is proportional to distance traveled. This problem is a special case of the weighted region problem and is a generalization of the well-known planar shortest path problem in the presence of obstacles. We present an Ο(n2) exact algorithm for this problem and faster algorithms for the cases of convex free regions and/or obstacles. We generalize our algorithm to allow arbitrary weights on the edges of the subdivision. In addition, we present algorithms to solve a variety of important applications: (1) an Ο(n2W) algorithm for finding lexicographically shortest paths in weighted regions (with W different weights); (2) an Ο(k2n2) algorithm for planning least-risk paths in a simple polygon that contains k line-of-sight threats (this becomes Ο(k4n4) in polygons with holes); and (3) an Ο(k2n3) algorithm for finding least-risk watchman routes in simple rectilinear polygons (a watchman route is such that each point in the polygon is visible from at least one point along the route).

This paper was published in "Linear Algebra and its Applications" 152 (1991) 93-105

Recent advances in the field of computational geometry have provided efficient algorithms for a variety of shortest path problems. Many problems in the field of terrain navigation can be cast as optimal path problems in a precise geometric model. With such a model one can develop and analyze algorithms for the solution of the original problem and can gain insights into how to design more efficient heuristics to deal with more complex problems. We examine the path planning problem in which we are given a “map” of a region of terrain and we are expected to find optimal paths from one point to another. This, for example, is a task which must be done repeatedly for the guidance of an autonomous vehicle. We examine how to formulate some path planning problems precisely, and we report algorithms to solve certain special cases.

We present an algorithm for determining the shortest path between a source and a destination through a planar subdivision in which each region has an associated weight. Distances are measured according to a weighted Euclidean metric: Each region of the subdivision has associated with it a weight, and the weighted distance between two points in a convex region is the product of the corresponding weight and the Euclidean distance between them. Our algorithm runs in time Ο(n7 L) and requires Ο(n3) space, where n is the number of edges of the subdivision, and L is the precision of the problem instance (including the number of bits in a user-specified tolerance ∈, which is the percentage the solution is allowed to differ from an optimal solution). The algorithm uses the fact that shortest paths obey Snell's Law of Refraction at region boundaries, a local optimality property of shortest paths that is well-known from the analogous optics model.

We present an algorithm for determining the shortest path between a source and a destination on an arbitrary (possibly nonconvex) polyhedral surface. The path is constrained to lie on the surface, and distances are measured according to the Euclidean metric. Our algorithm runs in time $O(n^2 \log n)$ and requires $O(n^2 )$ space, where n is the number of edges of the surface. After we run our algorithm, the distance from the source to any other destination may be determined using standard techniques in time $O(\log n)$ by locating the destination in the subdivision created by the algorithm. The actual shortest path from the source to a destination can be reported in time $O(k + \log n)$, where k is the number of faces crossed by the path. The algorithm generalizes to the case of multiple source points to build the Voronoi diagram on the surface, where n is now the maximum of the number of vertices and the number of sources.

This study describes the theoretical and practical aspects of the design and computer simulation of a heuristic based navigation algorithm. An algorithm is developed which provides a convenient testing system for generalized navigation strategies on a fixed map which may be known or unknown to a system. A variety of maps are simulated and the navigation results are compared.