We construct a probabilistic finite automaton (PFA) with 7 states and an input alphabet of 5 symbols for which the PFA Emptiness Problem is undecidable. The only input for the decision problem is the starting distribution. For the proof, we use reductions from special instances of the Post Correspondence Problem. We also consider some variations: The input alphabet of the PFA can be restricted to a binary alphabet at the expense of a larger number of states. If we allow a rational output value for each state instead of a yes-no acceptance decision, the number of states can even be reduced to 6.

Grid peeling is the process of repeatedly removing the convex hull vertices of the grid-points that lie inside a given convex curve. It has been conjectured that, for a more and more refined grid, grid peeling converges to a continuous process, the affine curve-shortening flow, which deforms the curve based on the curvature. We prove this conjecture for one class of curves, parabolas with a vertical axis, and we determine the value of the constant factor in the formula that relates the two processes.

Abstract A bipartite graph $$G=(U,V,E)$$ G = ( U , V , E ) is convex if the vertices in V can be linearly ordered such that for each vertex $$u\in U$$ u ∈ U , the neighbors of u are consecutive in the ordering of V. An induced matchingH of G is a matching for which no edge of E connects endpoints of two different edges of H. We show that in a convex bipartite graph with n vertices and mweighted edges, an induced matching of maximum total weight can be computed in $$O(n+m)$$ O ( n + m ) time. An unweighted convex bipartite graph has a representation of size O(n) that records for each vertex $$u\in U$$ u ∈ U the first and last neighbor in the ordering of V. Given such a compact representation, we compute an induced matching of maximum cardinality in O(n) time. In convex bipartite graphs, maximum-cardinality induced matchings are dual to minimum chain covers. A chain cover is a covering of the edge set by chain subgraphs, that is, subgraphs that do not contain induced matchings of more than one edge. Given a compact representation, we compute a representation of a minimum chain cover in O(n) time. If no compact representation is given, the cover can be computed in $$O(n+m)$$ O ( n + m ) time. All of our algorithms achieve optimal linear running time for the respective problem and model, and they improve and generalize the previous results in several ways: The best algorithms for the unweighted problem versions had a running time of $$O(n^2)$$ O ( n 2 ) (Brandstädt et al. in Theor. Comput. Sci. 381(1–3):260–265, 2007. 10.1016/j.tcs.2007.04.006 ). The weighted case has not been considered before.

Abstract What is the maximum number of intersections of the boundaries of a simple m-gon and a simple n-gon? This is a basic question in combinatorial geometry, and the answer is easy if at least one of m and n is even: If both m and n are even, then every pair of sides may cross and so the answer is mn. If exactly one polygon, say the n-gon, has an odd number of sides, it can intersect each side of the m-gon polygon at most $$n-1$$ n - 1 times; hence there are at most $$mn-m$$ m n - m intersections. It is not hard to construct examples that meet these bounds. If both m and n are odd, the best known construction has $$mn-(m+n)+3$$ m n - ( m + n ) + 3 intersections, and it is conjectured that this is the maximum. However, the best known upper bound is only $$mn-(m + \lceil {n}/{6} \rceil )$$ m n - ( m + ⌈ n / 6 ⌉ ) , for $$m \ge n$$ m ≥ n . We prove a new upper bound of $$mn-(m+n)+C$$ m n - ( m + n ) + C for some constant C, which is optimal apart from the value of C.

What is the maximum number of intersections of the boundaries of a simple m-gon and a simple n-gon, assuming general position? This is a basic question in combinatorial geometry, and the answer is easy if at least one of m and n is even. If both m and n are odd, the best known construction has mn-(m+n)+3 intersections, and it is conjectured that this is the maximum. However, the best known upper bound is only mn-(m + ⌈ n/6 ⌉), for m ≥ n. We prove a new upper bound of mn-(m+n)+C for some constant C, which is optimal apart from the value of C.

Abstract We study the following separation problem: Given a collection of pairwise disjoint coloured objects in the plane withkdifferent colours, compute a shortest “fence”F, i.e., a union of curves of minimum total length, that separates every pair of objects of different colours. Two objects are separated ifFcontains a simple closed curve that has one object in the interior and the other in the exterior. We refer to the problem asgeometrick-cut, as it is a geometric analog to the well-studied multicut problem on graphs. We first give an $$O(n^4\log ^3\!n)$$ O(n4log3n) -time algorithm that computes an optimal fence for the case where the input consists of polygons of two colours withncorners in total. We then show that the problem is NP-hard for the case of three colours. Finally, we give a randomised $$4/3\cdot 1.2965$$ 4/3·1.2965 -approximation algorithm for polygons and any number of colours.

We show that if a planar graph G has a plane straight-line drawing in which a subset S of its vertices are collinear, then for any set of points, X, in the plane with |X| = |S|, there is a plane straight-line drawing of G in which the vertices in S are mapped to the points in X. This solves an open problem posed by Ravsky and Verbitsky in 2008. In their terminology, we show that every collinear set is free. This result has applications in graph drawing, including untangling, column planarity, universal point subsets, and partial simultaneous drawings.

A tree with n vertices has at most 95n/13 minimal dominating sets. The growth constant is best possible. It is obtained in a semi-automatic way as a kind of “dominant eigenvalue” of a bilinear operation on sixtuples that is derived from the dynamic-programming recursion for computing the number of minimal dominating sets of a tree. We also derive an output-sensitive algorithm for listing all minimal dominating sets with linear set-up time and linear delay between successive solutions.

We introduce and study the problem Ordered Level Planarity, which asks for a planar drawing of a graph such that vertices are placed at prescribed positions in the plane and such that every edge is realized as a y -monotone curve. This can be interpreted as a variant of Level Planarity in which the vertices on each level appear in a prescribed total order. We establish a complexity dichotomy with respect to both the maximum degree and the level-width, that is, the maximum number of vertices that share a level. Our study of Ordered Level Planarity is motivated by connections to several other graph drawing problems. Geodesic Planarity asks for a planar drawing of a graph such that vertices are placed at prescribed positions in the plane and such that every edge e is realized as a polygonal path p composed of line segments with two adjacent directions from a given set S of directions that is symmetric with respect to the origin. Our results on Ordered Level Planarity imply NP -hardness for any S with ∣S∣ ≥ 4, even if the given graph is a matching. Manhattan Geodesic Planarity is the special case where S contains precisely the horizontal and vertical directions. Katz, Krug, Rutter, and Wolff claimed that Manhattan Geodesic Planarity can be solved in polynomial time for the special case of matchings [GD’09]. Our results imply that this is incorrect unless P = NP . Our reduction extends to settle the complexity of the Bi-Monotonicity problem, which was proposed by Fulek, Pelsmajer, Schaefer, and Štefankovič. Ordered Level Planarity turns out to be a special case of T-Level Planarity, Clustered Level Planarity, and Constrained Level Planarity. Thus, our results strengthen previous hardness results. In particular, our reduction to Clustered Level Planarity generates instances with only two non-trivial clusters. This answers a question posed by Angelini, Da Lozzo, Di Battista, Frati, and Roselli.

Our goal is to compare two planar point sets by finding subsets of a given size such that a minimum-weight matching between them has the smallest weight. This can be done by a translation of one set that minimizes the weight of the matching. We give efficient algorithms (a) for finding approximately optimal matchings, when the cost of a matching is the L_p-norm of the tuple of the Euclidean distances between the pairs of matched points, for any p in [1,infty], and (b) for constructing small-size approximate minimization (or matching) diagrams: partitions of the translation space into regions, together with an approximate optimal matching for each region.

Given a planar graph G and a partition of the neighbors of each vertex v in four sets v ↗ , v ↖ , v ↙ , and v ↘ , the problem W indrose P lanarity asks to decide whether G admits a windrose-planar drawing , that is, a planar drawing in which (i) each neighbor u ∈ v ↗ v is above and to the right of v , (ii) each neighbor u ∈ v ↖ is above and to the left of v , (iii) each neighbor u ∈ v ↙ is below and to the left of v , (iv) each neighbor u ∈ v ↘ is below and to the right of v , and (v) edges are represented by curves that are monotone with respect to each axis. By exploiting both the horizontal and the vertical relationship among vertices, windrose-planar drawings allow us to simultaneously visualize two partial orders defined by means of the edges of the graph. Although the problem is NP -hard in the general case, we give a polynomial-time algorithm for testing whether there exists a windrose-planar drawing that respects a given combinatorial embedding. This algorithm is based on a characterization of the plane triangulations admitting a windrose-planar drawing. Furthermore, for any embedded graph with n vertices that has a windrose-planar drawing, we can construct one with at most one bend per edge and with at most 2 n −5 bends in total, which lies on the 3 n × 3 n grid. The latter result contrasts with the fact that straight-line windrose-planar drawings may require exponential area.

Congruence is the geometric concept of being the same up to rotations and\ntranslations in Euclidean space. As congruence is a fundamental concept in\ngeometry, it has drawn broad attentions from the computational geometry\ncommunity for a long time whether the curse of dimensionality applies to\ncongruence testing. We developed a deterministic optimal-runningtime algorithm\nfor congruence testing in 4-space. To understand the importance of the main\nalgorithm in the historical context, we provide a survey about the\ncomputational model and the previous work on congruence testing algorithms.\nThe crucial ingredients of the algorithm are explained component by component.\nThese include general 4-dimensional rotations, angles between linear\nsubspaces, and the Plücker embedding. In the sequence of steps in the\nalgorithm, high regularities are forced in the structure of point sets. This\nlets us encounter beautiful mathematical structures on a 3-sphere and the\nsymmetry group of finite points: the Hopf fibration of a 3-sphere and the\nCoxeter group of four-dimensional point groups. We also give an elementary and\nself-contained overview about these two mathematical topics. The main\nalgorithm consists of five modules that are interesting in their own right.\nThe algorithm is complicated and we provide rather pessimistic estimates. This\nalgorithm, however, can be regarded as a big step forward to constructing a\nmore efficient algorithm in higher dimensions. In the same vein, the last part\nis devoted to the extendability of the algorithm to higher dimensions. This\npart concludes with discussing implementability and geometric properties that\nthe algorithm may imply.

Given a graph G=(V,E) with V={1,...,n}, we place on every vertex a token T_1,...,T_n. A swap is an exchange of tokens on adjacent vertices. We consider the algorithmic question of finding a shortest sequence of swaps such that token T_i is on vertex i. We are able to achieve essentially matching upper and lower bounds, for exact algorithms and approximation algorithms. For exact algorithms, we rule out any 2^{o(n)} algorithm under the ETH. This is matched with a simple 2^{O(n*log(n))} algorithm based on a breadth-first search in an auxiliary graph. We show one general 4-approximation and show APX-hardness. Thus, there is a small constant delta > 1 such that every polynomial time approximation algorithm has approximation factor at least delta. Our results also hold for a generalized version, where tokens and vertices are colored. In this generalized version each token must go to a vertex with the same color.

Given a planar graph G(V, E) and a partition of the neighbors of each vertex v ∊ V in four sets , and , the problem Windrose Planarity asks to decide whether G admits a windrose-planar drawing, that is, a planar drawing in which (i) each neighbor u ∊ is above and to the right of v, (ii) each neighbor u ∊ is above and to the left of v, (iii) each neighbor u ∊ is below and to the left of v, (iv) each neighbor u ∊ is below and to the right of v, and (v) edges are represented by curves that are monotone with respect to each axis. By exploiting both the horizontal and the vertical relationship among vertices, windrose-planar drawings allow to simultaneously visualize two partial orders defined by means of the edges of the graph. Although the problem is -hard in the general case, we give a polynomial-time algorithm for testing whether there exists a windrose-planar drawing that respects a combinatorial embedding that is given as part of the input. This algorithm is based on a characterization of the plane triangulations admitting a windrose-planar drawing. Furthermore, for any embedded graph admitting a windrose-planar drawing we show how to construct one with at most one bend per edge on an O(n) × O(n) grid. The latter result contrasts with the fact that straight-line windrose-planar drawings may require exponential area.

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.

Based on a simple parameterization of contact surfaces, we visualize both the workspace and the corresponding configuration space of a planar polygonal robot that moves amid planar polygonal obstacles.

It has been an open question whether the sum of finitely many isotropic Gaussian kernels in n ≥ 2 dimensions can have more modes than kernels, until in 2003 Carreira-Perpinan and Williams exhibited n+1 isotropic Gaussian kernels in Rn with n+2 modes. We give a detailed analysis of this example, showing that it has exponentially many critical points and that the resilience of the extra mode grows like √n. In addition, we exhibit finite configurations of isotropic Gaussian kernels with superlinearly many modes.

We study the problem how to draw a planar graph crossing-free such that every vertex is incident to an angle greater than π . In general a plane straight-line drawing cannot guarantee this property. We present algorithms which construct such drawings with either tangent-continuous biarcs or quadratic Bézier curves (parabolic arcs), even if the positions of the vertices are predefined by a given plane straight-line drawing of the graph. Moreover, the graph can be drawn with circular arcs if the vertices can be placed arbitrarily. The topic is related to non-crossing drawings of multigraphs and vertex labeling.

The problem of checking whether a given tower of bricks is stable can be easily answered by checking whether a system of linear inequalities has a feasible solution. A more challenging problem is to determine how an unstable tower of bricks collapses. We use Gauß’ principle of least restraint to show that this, and more general rigid-body simulation problems in which many parts touch each other, can be reduced to solving a sequence of convex quadratic programs, with linear constraints, corresponding to a discretization of time. The first of these quadratic programs gives an exact description of initial infinitesimal collapse. The results of the subsequent programs need to be integrated over time to yield an approximation of the global motion of the system.

We study the parameterized complexity of the k -center problem on a given n -point set P in ℝ d , with the dimension d as the parameter. We show that the rectilinear 3-center problem is fixed-parameter tractable, by giving an algorithm that runs in O ( n log n ) time for any fixed dimension d . On the other hand, we show that this is unlikely to be the case with both the Euclidean and rectilinear k -center problems for any k ≥ 2 and k ≥ 4 respectively. In particular, we prove that deciding whether P can be covered by the union of 2 balls of given radius or by the union of 4 cubes of given side length is W[1]-hard with respect to d , and thus not fixed-parameter tractable unless FPT=W[1]. For the Euclidean case, we also show that even an n o ( d ) -time algorithm does not exist, unless there is a 2 o ( n ) -time algorithm for n -variable 3SAT, that is, the Exponential Time Hypothesis fails.

We consider the problem of finding obnoxious centers in graphs. For arbitrary graphs with n vertices and m edges, we give a randomized algorithm with $O(n\log^{2}n+m\log n)$ expected time. For planar graphs, we give algorithms with $O(n\log n)$ expected time and $O(n\log^{3}n)$ worst-case time. For graphs with bounded treewidth, we give an algorithm taking $O(n\log n)$ worst-case time. The algorithms make use of parametric search and several results for computing distances on graphs of bounded treewidth and planar graphs.

Abstract For a surface in 3‐space that is represented by a set S of sample points, we construct a coarse approximating polytope P that uses a subset of S as its vertices and preserves the topology of . In contrast to surface reconstruction we do not use all the sample points, but we try to use as few points as possible. Such a polytope P is useful as a ‘seed polytope’ for starting an incremental refinement procedure to generate better and better approximations of based on interpolating subdivision surfaces or e.g. Bézier patches. Our algorithm starts from an r‐sample S of . Based on S, a set of surface covering balls with maximal radii is calculated such that the topology is retained. From the weighted α‐shape of a proper subset of these highly overlapping surface balls we get the desired polytope. As there is a rather large range for the possible radii for the surface balls, the method can be used to construct triangular surfaces from point clouds in a scalable manner. We also briefly sketch how to combine parts of our algorithm with existing medial axis algorithms for balls, in order to compute stable medial axis approximations with scalable level of detail.

A triangulation of a planar point set S is a maximal plane straight-line graph with vertex set S . In the minimum-weight triangulation (MWT) problem, we are looking for a triangulation of a given point set that minimizes the sum of the edge lengths. We prove that the decision version of this problem is NP-hard, using a reduction from PLANAR 1-IN-3-SAT. The correct working of the gadgets is established with computer assistance, using dynamic programming on polygonal faces, as well as the β-skeleton heuristic to certify that certain edges belong to the minimum-weight triangulation.

A finite planar point set P is called a magic configuration if there is an assignment of positive weights to the points of P such that, for everyline l determined by P, the sum of the weights of all points of P on l equals 1. We prove a conjecture of Murty from 1971 and show that a magic configuration consists either of points in general position, or all points are collinear, with the possible exception of one point, or they form a special configuration of 7 points.

Principal component analysis (PCA) is commonly used to compute a bounding box of a point set in Rd. The popularity of this heuristic lies in its speed, easy implementation and in the fact that usually, PCA bounding boxes quite well approximate the minimum-volume bounding boxes.Since there are examples of discrete points sets in the plane, showing that the worst case ratio of the volume ofthe PCA bounding box and the volume of the minimum-volume bounding box tends to infinity,we consider PCA bounding boxes for continuous sets, especially for the convex hull of a point set. Here, we contributenew upper bounds on the approximation factor of PCA bounding boxesof convex sets in R2 and R3.

We show how to embed a 3-connected planar graph with n verticesas a 3-polytope with small integer coordinates.The coordinates are bounded by O(27.55n). The crucial part is the construction of a plane embeddingwhich supports an equilibrium stress.We have to guarantee that the size of the coordinates and thestresses are small.This is achieved by applying Tutte's spring embedding method carefully.

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.

Article Share on Minimum weight triangulation is NP-hardSCG '06: Proceedings of the twenty-second annual symposium on Computational geometryJune 2006 Pages 1–10https://doi.org/10.1145/1137856.1137859Online:05 June 2006Publication History 11citation530DownloadsMetricsTotal Citations11Total Downloads530Last 12 Months4Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

We consider the problem of reconfiguring a linkage of rigid straight segments from a given start to a given target position with a continuous nonintersecting motion. The problem is nontrivial even for trees in two dimensions since it is known that not all configurations can be reconfigured to a straight position. We show that deciding reconfigurability for trees in two dimensions and for chains in three dimensions is PSPACE-complete.

Randomized incremental constructions are widely used in computational geometry, but they perform very badly on large data because of their inherently random memory access patterns. We define a biased randomized insertion order which removes enough randomness to significantly improve performance, but leaves enough randomness so that the algorithms remain theoretically optimal.

Pointed pseudo-triangulations are planar minimally rigid graphs embedded in the plane with pointed vertices (incident to an angle larger than p). In this paper we prove that the opposite statement is also true, namely that planar minimally rigid graphs always admit pointed embeddings, even under certain natural topological and combinatorial constraints. The proofs yield efficient embedding algorithms. They also provide---to the best of our knowledge---the first algorithmically effective result on graph embeddings with oriented matroid constraints other than convexity of faces.

Given a polygonal curve and a geometric graph, we describe an efficient algorithm to find a path in the graph which is most similar to the curve, using the well-known Fréchet distance for curves.

I will survey some recent results about unfolding of linkages and connections to pseudotriangulations.

The obnoxious center problem in a graph G asks for a location on an edge of the graph such that the minimum weighted distance from this point to a vertex of the graph is as large as possible. We derive algorithms with linear running time for the cases when G is a path or a star, thus improving previous results of Tamir [SIAMJ. Discrete Math, 1 (1988), pp. 377--396]. For subdivided stars we present an algorithm of running time O(n log n). For general trees, we improve an algorithm of Tamir [SIAM J. Discrete Math, 1 (1988), pp. 377--396] by a factor of log n. Moreover, a linear algorithm for the unweighted center problem on an arbitrary tree with neutral and obnoxious vertices is described.

Consider a planar linkage, consisting of disjoint polygonal arcs and cycles of rigid bars joined at incident endpoints (polygonal chains), with the property that no cycle surrounds another arc or cycle. We prove that the linkage can be continuously moved so that the arcs become straight, the cycles become convex, and no bars cross while preserving the bar lengths. Furthermore, our motion is piecewise-differentiable, does not decrease the distance between any pair of vertices, and preserves any symmetry present in the initial configuration. In particular this result settles the well-studied carpenter's rule conjecture.

We consider the problem of constructing prefix-free codes of minimum cost when the encoding alphabet contains letters of unequal length. The complexity of this problem has been unclear for thirty years with the only algorithm known for its solution involving a transformation to integer linear programming. We introduce a new dynamic programming solution to the problem. It optimally encodes n words in O(n/sup C+2/) time, if the costs of the letters are integers between 1 and C. While still leaving open the question of whether the general problem is solvable in polynomial time, our algorithm seems to be the first one that runs in polynomial time for fixed letter costs.

We show that there is a matching between the edges of anytwo triangulations of a planar point set such that an edge of one triangulation is matched either to the identical edge in the other triangulation or to an edge that crosses it. This theorem also holds for the triangles of the triangulations and in general independence systems. As an application, we give some lower bounds for the minimumweight triangulation which can be computed in polynomial time by matching and network #ow techniques. We exhibit an easy-to-recognize class of point sets for which the minimum-weight triangulation coincides with the greedy triangulation. 1 Introduction The aim of this paper is to prove and discuss some surprising and rather general intersection properties of planar triangulations. Given two triangulations of a point set, we can #nd a matching between their edge sets such that matched edges either cross or coincide. This theorem and a few related statements will be proved in Section 2. T...

For two given point sets, we present a very simple (almost trivial) algorithm to translate one set so that the Hausdorff distance between the two sets is not larger than a constant factor times the minimum Hausdorff distance which can be achieved in this way. The algorithm just matches the so-called Steiner points of the two sets.

Article Free Access Share on Degenerate convex hulls in high dimensions without extra storage Author: Günter Rote View Profile Authors Info & Claims SCG '92: Proceedings of the eighth annual symposium on Computational geometryJuly 1992 Pages 26–32https://doi.org/10.1145/142675.142685Online:01 July 1992Publication History 5citation302DownloadsMetricsTotal Citations5Total Downloads302Last 12 Months4Last 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 SiteeReaderPDF

For compact Euclidean bodiesP, Q, we define λ(P, Q) to be the smallest ratior/s wherer > 0,s > 0 satisfy $$sQ' \subseteq P \subseteq rQ''$$ . HeresQ denotes a scaling ofQ by the factors, andQ′,Q″ are some translates ofQ. This function λ gives us a new distance function between bodies which, unlike previously studied measures, is invariant under affine transformations. If homothetic bodies are identified, the logarithm of this function is a metric. (Two bodies arehomothetic if one can be obtained from the other by scaling and translation.) For integerk ≥ 3, define λ(k) to be the minimum value such that for each convex polygonP there exists a convexk-gonQ with λ(P, Q) ≤ λ(k). Among other results, we prove that 2.118 ... <-λ(3) ≤ 2.25 and λ(k) = 1 + Θ(k −2). We give anO(n 2 log2 n)-time algorithm which, for any input convexn-gonP, finds a triangleT that minimizes λ(T, P) among triangles. However, in linear time we can find a trianglet with λ(t, P)<-2.25. Our study is motivated by the attempt to reduce the complexity of the polygon containment problem, and also the motion-planning problem. In each case we describe algorithms which run faster when certain implicitslackness parameters of the input are bounded away from 1. These algorithms illustrate a new algorithmic paradigm in computational geometry for coping with complexity.

Abstract The special case of the Euclidean traveling salesman problem, where the n given points lie on a small number (N) of parallel lines in the plane, is solved by a dynamic programming approach in time n N , for fixed N , i.e., in polynomial time. This extends a result of Cutler (1980) for three lines. Such problems arise, for example, in the fabrication of printed circuit boards, where the distance traveled by a laser that drills holes in certain places of the board should be minimized. The parallelity condition can be relaxed to point sets that lie on N “almost parallel” line segments. We give a characterization of the allowed segment configurations by a set of forbidden subconfigurations.

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.