This repository contains benchmark instances for (s,t)-max-flow/min-cut, which were submitted to the 13th DIMACS Implementation Challenge. The instances are derived from the bicriteria polygon aggregation problem, which is studied in the following publications: Bicriteria Shapes: Hierarchical Grouping and Aggregation of Polygons with an Efficient Graph-Cut Approach. Peter Rottmann, Anne Driemel, Herman Haverkort, Heiko Röglin, Jan-Henrik Haunert. In: ACM Transactions on Spatial Algorithms and Systems, vol. 11(1), ACM, pages 3:1--3:23, 2025. A Simpler Approach for Monotone Parametric Minimum Cut: Finding the Breakpoints in Order. Arne Beines, Michael Kaibel, Philip Mayer, Petra Mutzel, Jonas Sauer. In: Proceedings of the 27th Workshop on Algorithm Engineering and Experiments (ALENEX'25), SIAM, pages 29--41, 2025. Bicriteria Polygon Aggregation with Arbitrary Shapes. Lotte Blank, David Eppstein, Jan-Henrik Haunert, Herman Haverkort, Benedikt Kolbe, Philip Mayer, Petra Mutzel, Alexander Naumann, Jonas Sauer. To appear in: Proceedings of the 34th Annual European Symposium on Algorithms (ESA'26), Leibniz International Proceedings in Informatics, 2026. Background These instances are derived from a real-world application: polygon aggregation for map simplification. Given is a set $P$ of building footprints, represented as 2D polygons. The objective is to find a set $S$ of interior-disjoint representative regions, such that each polygon in $P$ is fully contained in a region of $S$. We are interested in a solution that minimizes the objective function $g_\alpha(S) = A(S) + \alpha \cdot P(S)$, where $A(S)$ and $P(S)$ are the total area and perimeter of the regions in $S$, respectively. The parameter $\alpha$ controls the trade-off between faithfulness to the input (represented by the area) and shape simplicity (represented by the perimeter). In a cartographic application, it can be thought of as the "zoom factor" -- the further we zoom out, the simpler we want the shapes to become. We distinguish between two variants of the problem, both for a fixed choice of $\alpha$: Subdivision-based: A subdivision $D$ of the plane (e.g., a constrained Delaunay triangulation) is supplied in advance, such that each polygon in $P$ appears as a cell of $D$. The solution must be constructed by selecting cells from $D$ to add to $P$. The problem is solved via a transformation to (s,t)-min-cut on an augmented geometric dual of $D$ (see any of the papers listed above for details). Unrestricted: No restrictions are made regarding the shape of $S$ -- the only conditions are that $P$ must be covered and that the objective function $g_\alpha(S)$ is minimized. Blank et al. show that in this variant, the polygons are connected by circular arcs of radius $\alpha$ that fulfill several other conditions. The arcs are chosen from a set of $O(n^2)$ candidates. The problem can then be solved optimally via a transformation to the subdivision-based case, where the subdivision $D$ is created by superimposing all $O(n^2)$ arcs. This yields a solution in polynomial time, although the subdivision is much more complex than the constrained Delaunay triangulation. The resulting instances have some similarities with grid-based computer vision max-flow instances, which are built using a similar geometric-dual construction: They are sparse and have short (s,t)-paths. However, unlike typical vision instances, they do not have a regular structure because they are derived from human settlement areas. Consequently, although all nodes (except for s and t) have low degrees, the degrees are not entirely uniform. For the unrestricted variant, the graph is highly detailed because it is derived from a geometric intersection process between many circular arcs. As a side note, a parametric version of the problem, where $\alpha$ is not fixed, has also been studied. Here, the objective is to find an optimal solution for every possible value of $\alpha$. Beines et al. show that, with an equivalent reformulation of the objective function $g_\alpha$, this is a monotone parametric min-cut problem. The instances in this dataset are not parametric, but parametric instances can be found here. Contents The dataset is split into two groups, depending on how the subdivision was built: triangulations: Using a constrained Delaunay triangulation, as proposed by Rottmann et al. The instances are cities of varying sizes (Bonn, Cologne, Berlin, Miami) and the entire German state of Saarland. For each instance, there are five copies, with the different $\alpha$ values 100, 500, 1000, 5000, and 25000. Note that the graph structure is the same for all copies; only the weights are different. arcs: Using the geometric intersection of the candidate arcs, as proposed by Blank et al. for the unrestricted variant. The instances represent the towns of Ahrem, Edendorf, Friesheim and Gerolstein in the German state of North Rhine-Westphalia. For each instance, there are four copies, with the different $\alpha$ values 100, 500, 1000, 5000. Note that for this variant, the graph size increases dramatically with $\alpha$. The arc capacities represent a weighted tradeoff between area and perimeter, measured in square decimeters (dm^2) and rounded to the nearest integer. The $\alpha$ parameter is also measured in decimeters. In the arcs instances, this corresponds to the radii of the circular arcs from which the subdivision is formed, e.g., $\alpha=5000$ represents arcs with radii of 500m. Data Sources Ahrem, Friesheim, Edendorf, Gerolstein, Bonn, Cologne: OpenStreetMap data from Geofabrik Saarland: OpenStreetMap data from Geofabrik Berlin, Miami: GHS-OBAT project Format The files follow the format from the first DIMACS implementation challenge. This is a text format in which each line is prefixed with a character that specifies the type of line. Lines starting with c are comments and should be ignored. The first non-comment line is the problem line: p max NODES ARCS Here, max is the problem type (max-flow/min-cut), NODES is the number of nodes in the network, and ARCS is the number of directed arcs. This is followed by two node descriptor lines:n IDT tn IDS s Here, IDT is the id of the sink node and IDS is the id of the source node. Note that in this format, node ids start at 1. Finally, there is an arc descriptor line for every directed arc in the network: a SRC DST C This specifies an arc from node SRC to DST with capacity C. Capacities with values of int32_max or more should be interpreted as infinite. Note that the format does not require that a reverse arc exists for every directed arc. If reverse arcs are required by your algorithm, you must ensure that missing arcs are added with capacity 0. Credits and Contact This dataset was created by two research groups at the University of Bonn: the geoinformation group headed by Prof. Dr. Jan-Henrik Haunert and the Computational Analytics group headed by Prof. Dr. Petra Mutzel. It is released under the MIT license. When using it, please cite the publications listed above. If you want to report problems or give feedback on the dataset, please contact Jonas Sauer ([email protected]).

In this paper we present an algorithmic framework for solving a class of combinatorial optimization problems on graphs with bounded pathwidth. The problems are NP-hard in general, but solvable in linear time on this type of graphs. The problems are relevant for assessing network reliability and improving the network's performance and fault tolerance. The main technique considered in this paper is dynamic programming.

A witness drawing of a graph is a visualization that clearly shows a given property of a graph. We study and implement various drawing paradigms for witness drawings to clearly show that graphs have bounded pathwidth or treewidth. Our approach draws the tree decomposition or path decomposition as a tree of bags, with induced subgraphs shown in each bag, and with "tracks" for each graph vertex connecting its copies in multiple bags. Within bags, we optimize the vertex layout to avoid crossings of edges and tracks. We implement a visualization prototype for crossing minimization using dynamic programming for graphs of small width and heuristic approaches for graphs of larger width. We introduce a taxonomy of drawing styles, which render the subgraph for each bag as an arc diagram with one or two pages or as a circular layout with straight-line edges, and we render tracks either with straight lines or with orbital-radial paths.

A string graph is the intersection graph of curves in the plane. Kratochvíl previously showed the existence of infinitely many obstacles: graphs that are not string graphs but for which any edge contraction or vertex deletion produces a string graph. Kratochvíl’s obstacles contain arbitrarily large cliques, so they have girth three and unbounded degree. We extend this line of working by studying obstacles among graphs of restricted girth and/or degree. We construct an infinite family of obstacles of girth four; in addition, our construction is K_{2,3}-subgraph-free and near-planar (planar plus one edge). Furthermore, we prove that there is a subcubic obstacle of girth three, and that there are no subcubic obstacles of high girth. We characterize the subcubic string graphs as having a matching whose contraction yields a planar graph, and based on this characterization we find a linear-time algorithm for recognizing subcubic string graphs of bounded treewidth.

We prove that, for every plane graph G and every smooth convex curve C not on a single line, there exists a straight-line drawing of G for which every face is crossed by C.

Much prior work has been done on designing computational geometry algorithms that handle input degeneracies, data imprecision, and arithmetic round-off errors. We take a new approach, inspired by the noisy sorting literature, and study computational geometry algorithms subject to noisy Boolean primitive operations in which, e.g., the comparison "is point q above line 𝓁?" returns the wrong answer with some fixed probability. We propose a novel technique called path-guided pushdown random walks that generalizes the results of noisy sorting. We apply this technique to solve point-location, plane-sweep, convex hulls in 2D and 3D, and Delaunay triangulations for noisy primitives in optimal time with high probability.

Abstract We describe a polynomial time algorithm that takes as input a polygon with axis-parallel sides but irrational vertex coordinates, and outputs a set of as few rectangles as possible into which it can be dissected by axis-parallel cuts and translations. The number of rectangles is the rank of the Dehn invariant of the polygon. The same method can also be used to dissect an axis-parallel polygon into a simple polygon with the minimum possible number of edges. When rotations or reflections are allowed, we can approximate the minimum number of rectangles to within a factor of two.

Abstract We show that, for planar point sets, the number of non-crossing Hamiltonian paths is polynomially bounded in the number of non-crossing paths, and the number of non-crossing Hamiltonian cycles (polygonalizations) is polynomially bounded in the number of surrounding cycles. As a consequence, we can list the non-crossing Hamiltonian paths or the polygonalizations, in time polynomial in the output size, by filtering the output of simple backtracking algorithms for non-crossing paths or surrounding cycles respectively. We do not assume that the points are in general position. To prove these results we relate the numbers of non-crossing structures to two easily-computed parameters of the point set: the minimum number of points whose removal results in a collinear set, and the number of points interior to the convex hull. These relations also lead to polynomial-time approximation algorithms for the numbers of structures of all four types, accurate to within a constant factor of the logarithm of these numbers.

Abstract. Alon, Seymour, and Thomas [ J. Amer. Math. Soc., 3 (1990), pp. 801–808] proved that every [Formula: see text]-vertex graph excluding [Formula: see text] as a minor has treewidth less than [Formula: see text]. Illingworth, Scott, and Wood [ Product Structure of Graphs with an Excluded Minor, preprint, arXiv:2104.06627 , 2022] recently refined this result by showing that every such graph is a subgraph of some graph with treewidth [Formula: see text], where each vertex is blown up by a complete graph of order [Formula: see text]. Solving an open problem of Illingworth, Scott, and Wood [2022], we prove that the treewidth bound can be reduced to 4 while keeping blowups of order [Formula: see text]. As an extension of the Lipton–Tarjan theorem, in the case of planar graphs, we show that the treewidth can be further reduced to 2, which is best possible. We generalize this result for [Formula: see text]-minor-free graphs, with blowups of order [Formula: see text]. This setting includes graphs embeddable on any fixed surface.

We show that, for planar point sets, the number of non-crossing Hamiltonian paths is polynomially bounded in the number of non-crossing paths, and the number of non-crossing Hamiltonian cycles (polygonalizations) is polynomially bounded in the number of surrounding cycles. As a consequence, we can list the non-crossing Hamiltonian paths or the polygonalizations, in time polynomial in the output size, by filtering the output of simple backtracking algorithms for non-crossing paths or surrounding cycles respectively. To prove these results we relate the numbers of non-crossing structures to two easily-computed parameters of the point set: the minimum number of points whose removal results in a collinear set, and the number of points interior to the convex hull. These relations also lead to polynomial-time approximation algorithms for the numbers of structures of all four types, accurate to within a constant factor of the logarithm of these numbers.

We give a new rapid mixing result for a natural random walk on the independent sets of a graph $G$. We show that when $G$ has bounded treewidth, this random walk -- known as the Glauber dynamics for the hardcore model -- mixes rapidly for all fixed values of the standard parameter $λ> 0$, giving a simple alternative to existing sampling algorithms for these structures. We also show rapid mixing for analogous Markov chains on dominating sets, $b$-edge covers, $b$-matchings, maximal independent sets, and maximal $b$-matchings. (For $b$-matchings, maximal independent sets, and maximal $b$-matchings we also require bounded degree.) Our results imply simpler alternatives to known algorithms for the sampling and approximate counting problems in these graphs. We prove our results by applying a divide-and-conquer framework we developed in a previous paper, as an alternative to the projection-restriction technique introduced by Jerrum, Son, Tetali, and Vigoda. We extend this prior framework to handle chains for which the application of that framework is not straightforward, strengthening existing results by Dyer, Goldberg, and Jerrum and by Heinrich for the Glauber dynamics on $q$-colorings of graphs of bounded treewidth and bounded degree.

Abstract We prove that, for an undirected graph with n vertices and m edges, each labeled with a linear function of a parameter $$\lambda $$ λ , the number of different minimum spanning trees obtained as the parameter varies can be $$\Omega (m\log n)$$ Ω ( m log n ) .

Resolving an open question from 2006, we prove the existence of light-weight bounded-degree (1+ε)-spanners for unit ball graphs in the metrics of bounded doubling dimension, and we design a simple O(log*n)-round distributed algorithm in the LOCAL model for finding such spanners using only 2-hop neighborhood information. We further study the problem in the two dimensional Euclidean plane and we propose a construction with similar properties that has a low-intersection property as well. Lastly, we provide experimental results that confirm the performance of our algorithms.

Resolving an open question from 2006 [Damian et al., 2006], we prove the existence of light-weight bounded-degree spanners for unit ball graphs in the metrics of bounded doubling dimension, and we design a simple 𝒪(log^*n)-round distributed algorithm in the LOCAL model of computation, that given a unit ball graph G with n vertices and a positive constant ε < 1 finds a (1+ε)-spanner with constant bounds on its maximum degree and its lightness using only 2-hop neighborhood information. This immediately improves the best prior lightness bound, the algorithm of Damian, Pandit, and Pemmaraju [Damian et al., 2006], which runs in 𝒪(log^*n) rounds in the LOCAL model, but has a 𝒪(log Δ) bound on its lightness, where Δ is the ratio of the length of the longest edge to the length of the shortest edge in the unit ball graph. Next, we adjust our algorithm to work in the CONGEST model, without changing its round complexity, hence proposing the first spanner construction for unit ball graphs in the CONGEST model of computation. We further study the problem in the two dimensional Euclidean plane and we provide a construction with similar properties that has a constant average number of edge intersections per node. Lastly, we provide experimental results that confirm our theoretical bounds, and show an efficient performance from our distributed algorithm compared to the best known centralized construction.

The objective of the well-known Tower of Hanoi puzzle is to move a set of discs one at a time from one of a set of pegs to another, while keeping the discs sorted on each peg. We propose an adversarial variation in which the first player forbids a set of states in the puzzle, and the second player must then convert one randomly-selected state to another without passing through forbidden states. Analyzing this version raises the question of the treewidth of Hanoi graphs. We find this number exactly for three-peg puzzles and provide nearly-tight asymptotic bounds for larger numbers of pegs.

$t$-spanners are used to approximate the pairwise distances between a set of points in a metric space. They have only a few edges compared to the total number of pairs and they provide a $t$-approximation on the distance of any two arbitrary points. There are many ways to construct such graphs and one of the most efficient ones, in terms of weight and the number of edges of the resulting graph, is the greedy spanner. In this paper, we study the edge crossings of the greedy spanner for points in the Euclidean plane. We prove a constant upper bound for the number of intersections with larger edges that only depends on the stretch factor of the spanner, $t$, and we show there can be more than a bounded number of intersections with smaller edges. Our results imply that greedy spanners for points in the plane have separators of size $\mathcal{O}(\sqrt n)$, that their planarizations have linear size, and that a separator hierarchy for these graphs can be constructed from their planarizations in linear time.

Abstract For a clustered graph, i.e, a graph whose vertex set is recursively partitioned into clusters, the C-Planarity Testing problem asks whether it is possible to find a planar embedding of the graph and a representation of each cluster as a region homeomorphic to a closed disk such that (1) the subgraph induced by each cluster is drawn in the interior of the corresponding disk, (2) each edge intersects any disk at most once, and (3) the nesting between clusters is reflected by the representation, i.e., child clusters are properly contained in their parent cluster. The computational complexity of this problem, whose study has been central to the theory of graph visualization since its introduction in 1995 [Feng, Cohen, and Eades, Planarity for clustered graphs, ESA’95], has only been recently settled [Fulek and Tóth, Atomic Embeddability, Clustered Planarity, and Thickenability, to appear at SODA’20]. Before such a breakthrough, the complexity question was still unsolved even when the graph has a prescribed planar embedding, i.e, for embedded clustered graphs. We show that the C-Planarity Testing problem admits a single-exponential single-parameter FPT (resp., XP) algorithm for embedded flat (resp., non-flat) clustered graphs, when parameterized by the carving-width of the dual graph of the input. These are the first FPT and XP algorithms for this long-standing open problem with respect to a single notable graph-width parameter. Moreover, the polynomial dependency of our FPT algorithm is smaller than the one of the algorithm by Fulek and Tóth. In particular, our algorithm runs in quadratic time for flat instances of bounded treewidth and bounded face size. To further strengthen the relevance of this result, we show that an algorithm with running time O(r(n)) for flat instances whose underlying graph has pathwidth 1 would result in an algorithm with running time O(r(n)) for flat instances and with running time $$O(r(n^2) + n^2)$$ O ( r ( n 2 ) + n 2 ) for general, possibly non-flat, instances.

In 1988, Vazirani gave an NC algorithm for computing the number of perfect matchings in $K_{3,3}$-minor-free graphs by building on Kasteleyn's scheme for planar graphs, and stated that this “opens up the possibility of obtaining an NC algorithm for finding a perfect matching in $K_{3,3}$-free graphs.” In this paper, we finally settle this 30-year-old open problem. Building on recent NC algorithms for planar and bounded-genus perfect matching by Anari and Vazirani and later by Sankowski, we obtain NC algorithms for perfect matching in any minor-closed graph family that forbids a one-crossing graph. This family includes several well-studied graph families including the $K_{3,3}$-minor-free graphs and $K_5$-minor-free graphs. Graphs in these families not only have unbounded genus, but can have genus as high as $O(n)$. Our method applies as well to several other problems related to perfect matching. In particular, we obtain NC algorithms for the following problems in any family of graphs (or networks) with a one-crossing forbidden minor: (1) Determining whether a given graph has a perfect matching and, if so, finding one. (2) Finding a minimum-weight perfect matching in the graph, assuming that the edge weights are polynomially bounded. (3) Finding a maximum $st$-flow in the network, with arbitrary capacities. The main new idea enabling our results is the definition and use of matching-mimicking networks, small replacement networks that behave the same with respect to matching problems involving a fixed set of terminals, as the larger network they replace.

We prove that a minor-closed class of graphs has bounded layered pathwidth if and only if some apex-forest is not in the class. This generalizes a theorem of Robertson and Seymour, which says that a minor-closed class of graphs has bounded pathwidth if and only if some forest is not in the class.

We prove that it is #P-complete to count the triangulations of a (non-simple) polygon.

We consider the NP-complete problem of tracking paths in a graph, first introduced by Banik et. al. [3]. Given an undirected graph with a source $s$ and a destination $t$, find the smallest subset of vertices whose intersection with any $s-t$ path results in a unique sequence. In this paper, we show that this problem remains NP-complete when the graph is planar and we give a 4-approximation algorithm in this setting. We also show, via Courcelle's theorem, that it can be solved in linear time for graphs of bounded-clique width, when its clique decomposition is given in advance.

We show new applications of the nearest-neighbor chain algorithm, a technique that originated in agglomerative hierarchical clustering. We apply it to a diverse class of geometric problems: we construct the greedy multi-fragment tour for Euclidean TSP in $O(n\log n)$ time in any fixed dimension and for Steiner TSP in planar graphs in $O(n\sqrt{n}\log n)$ time; we compute motorcycle graphs (which are a central part in straight skeleton algorithms) in $O(n^{4/3+\varepsilon})$ time for any $\varepsilon>0$; we introduce a narcissistic variant of the $k$-attribute stable matching model, and solve it in $O(n^{2-4/(k(1+\varepsilon)+2)})$ time; we give a linear-time $2$-approximation for a 1D geometric set cover problem with applications to radio station placement.

For a clustered graph, i.e, a graph whose vertex set is recursively partitioned into clusters, the C-Planarity Testing problem asks whether it is possible to find a planar embedding of the graph and a representation of each cluster as a region homeomorphic to a closed disk such that 1. the subgraph induced by each cluster is drawn in the interior of the corresponding disk, 2. each edge intersects any disk at most once, and 3. the nesting between clusters is reflected by the representation, i.e., child clusters are properly contained in their parent cluster. The computational complexity of this problem, whose study has been central to the theory of graph visualization since its introduction in 1995 [Feng, Cohen, and Eades, Planarity for clustered graphs, ESA'95], has only been recently settled [Fulek and Tóth, Atomic Embeddability, Clustered Planarity, and Thickenability, to appear at SODA'20]. Before such a breakthrough, the complexity question was still unsolved even when the graph has a prescribed planar embedding, i.e, for embedded clustered graphs. We show that the C-Planarity Testing problem admits a single-exponential single-parameter FPT algorithm for embedded clustered graphs, when parameterized by the carving-width of the dual graph of the input. This is the first FPT algorithm for this long-standing open problem with respect to a single notable graph-width parameter. Moreover, in the general case, the polynomial dependency of our FPT algorithm is smaller than the one of the algorithm by Fulek and Tóth. To further strengthen the relevance of this result, we show that the C-Planarity Testing problem retains its computational complexity when parameterized by several other graph-width parameters, which may potentially lead to faster algorithms.

We consider decomposing a 3-connected planar graph G using laminar separators of size three. We show how to find a maximal set of laminar 3-separators in such a graph in linear time. We also discuss how to find maximal laminar set of 3-separators from special families. For example we discuss non-trivial cuts, ie. cuts which split G into two components of size at least two. For any vertex v, we also show how to find a maximal set of 3-separators disjoint from v which are laminar and satisfy: every vertex in a separator X has two neighbours not in the unique component of G – X containing v. In all cases, we show how to construct a corresponding tree decomposition of adhesion three. Our new algorithms form an important component of recent methods for finding disjoint paths in nonplanar graphs.

In 1988, Vazirani gave an NC algorithm for computing the number of perfect matchings in K3,3-minor-free graphs by building on Kasteleyn's scheme for planar graphs, and stated that this "opens up the possibility of obtaining an NC algorithm for finding a perfect matching in K3,3-free graphs." In this paper, we finally settle this 30-year-old open problem. Building on recent NC algorithms for planar and bounded-genus perfect matching by Anari and Vazirani and by Sankowski, we obtain NC algorithms for perfect matching in any minor-closed graph family that forbids a one-crossing graph. This result applies to several well-studied graph families including the K3,3-minor-free graphs and K5-minor-free graphs. Graphs in these families not only have unbounded genus, but can have genus as high as O(n). Our method applies as well to several other problems related to perfect matching. In particular, we obtain NC algorithms for the following problems in any family of graphs (or networks) with a one-crossing forbidden minor: - Determining whether a given graph has a perfect matching and if so, finding one. - Finding a minimum weight perfect matching in the graph, assuming that the edge weights are polynomially bounded. - Computing the number of perfect matchings in the graph. - Finding a maximum st-flow in the network, with arbitrary capacities. The main new idea enabling our results is the definition and use of matching-mimicking networks, small replacement networks that behave the same, with respect to matching problems involving a fixed set of terminals, as the larger network they replace.

In this paper we study an experimentally-observed connection between two seemingly unrelated processes, one from computational geometry and the other from differential geometry. The first one (which we call grid peeling) is the convex-layer decomposition of subsets G ⊂ ℤ2 of the integer grid, previously studied for the particular case G = {1, …, m}2 by Har-Peled and Lidický (2013). The second one is the affine curve-shortening flow (ACSF), first studied by Alvarez et al. (1993) and Sapiro and Tannenbaum (1993). We present empirical evidence that, in a certain well-defined sense, grid peeling behaves at the limit like ACSF on convex curves. We offer some theoretical arguments in favor of this conjecture. We also pay closer attention to the simple case where G = ℕ2 is a quarter-infinite grid. This case corresponds to ACSF starting with an infinite L-shaped curve, which when transformed using the ACSF becomes a hyperbola for all times t > 0. We prove that, in the grid peeling of ℕ2, (1) the number of grid points removed up to iteration n is Θ(n3/2 log n); and (2) the boundary at iteration n is sandwiched between two hyperbolas that are separated from each other by a constant factor.

We empirically study sorting in the evolving data model. In this model, a sorting algorithm maintains an approximation to the sorted order of a list of data items while simultaneously, with each comparison made by the algorithm, an adversary randomly swaps the order of adjacent items in the true sorted order. Previous work studies only two versions of quicksort, and has a gap between the lower bound of Ω(n) and the best upper bound of O(n log log n). The experiments we perform in this paper provide empirical evidence that some quadratic-time algorithms such as insertion sort and bubble sort are asymptotically optimal for any constant rate of random swaps. In fact, these algorithms perform as well as or better than algorithms such as quicksort that are more efficient in the traditional algorithm analysis model.

We give optimal sorting algorithms in the evolving data framework, where an algorithm's input data is changing while the algorithm is executing. In this framework, instead of producing a final output, an algorithm attempts to maintain an output close to the correct output for the current state of the data, repeatedly updating its best estimate of a correct output over time. We show that a simple repeated insertion-sort algorithm can maintain an O(n) Kendall tau distance, with high probability, between a maintained list and an underlying total order of n items in an evolving data model where each comparison is followed by a swap between a random consecutive pair of items in the underlying total order. This result is asymptotically optimal, since there is an Omega(n) lower bound for Kendall tau distance for this problem. Our result closes the gap between this lower bound and the previous best algorithm for this problem, which maintains a Kendall tau distance of O(n log log n) with high probability. It also confirms previous experimental results that suggested that insertion sort tends to perform better than quicksort in practice.

The k-leaf power graph G of a tree T is a graph whose vertices are the leaves of T and whose edges connect pairs of leaves at unweighted distance at most k in T. Recognition of the k-leaf power graphs for k >= 6 is still an open problem. In this paper, we provide an algorithm for this problem for sparse leaf power graphs. Our result shows that the problem of recognizing these graphs is fixed-parameter tractable when parameterized both by k and by the degeneracy of the given graph. To prove this, we describe how to embed the leaf root of a leaf power graph into a product of the graph with a cycle graph. We bound the treewidth of the resulting product in terms of k and the degeneracy of G. As a result, we can use methods based on monadic second-order logic (MSO_2) to recognize the existence of a leaf power as a subgraph of the product graph.

We consider problems where the input is a set of points in the plane and an integer $k$, and the task is to find a subset $S$ of the input points of size $k$ such that $S$ satisfies some property. We focus on properties that depend only on the order type of the points and are monotone under point removals. We show that not all such problems are fixed-parameter tractable parameterized by $k$, by exhibiting a property defined by three forbidden patterns for which finding a $k$-point subset with the property is $\mathrm{W}[1]$-complete and (assuming the exponential time hypothesis) cannot be solved in time $n^{o(k/\log k)}$. However, we show that problems of this type are fixed-parameter tractable for all properties that include all collinear point sets, properties that exclude at least one convex polygon, and properties defined by a single forbidden pattern.

We define the parametric closure problem , in which the input is a partially ordered set whose elements have linearly varying weights and the goal is to compute the sequence of minimum-weight downsets of the partial order as the weights vary. We give polynomial time solutions to many important special cases of this problem including semiorders, reachability orders of bounded-treewidth graphs, partial orders of bounded width, and series-parallel partial orders. Our result for series-parallel orders provides a significant generalization of a previous result of Carlson and Eppstein on bicriterion subtree problems.

We define the crossing graph of a given embedded graph (such as a road network) to be a graph with a vertex for each edge of the embedding, with two crossing graph vertices adjacent when the corresponding two edges of the embedding cross each other. In this paper, we study the sparsity properties of crossing graphs of real-world road networks. We show that, in large road networks (the Urban Road Network Dataset), the crossing graphs have connected components that are primarily trees, and that the remaining non-tree components are typically sparse (technically, that they have bounded degeneracy). We prove theoretically that when an embedded graph has a sparse crossing graph, it has other desirable properties that lead to fast algorithms for shortest paths and other algorithms important in geographic information systems. Notably, these graphs have polynomial expansion, meaning that they and all their subgraphs have small separators.

We introduce a novel method for defining geographic districts in road networks using stable matching. In this approach, each geographic district is defined in terms of a center, which identifies a location of interest, such as a post office or polling place, and all other network vertices must be labeled with the center to which they are associated. We focus on defining geographic districts that are equitable, in that every district has the same number of vertices and the assignment is stable in terms of geographic distance. That is, there is no unassigned vertex-center pair such that both would prefer each other over their current assignments. We solve this problem using a version of the classic stable matching problem, called symmetric stable matching, in which the preferences of the elements in both sets obey a certain symmetry. We show that, for a planar graph or road network with n nodes and k centers, the problem can be solved in O(n √ n log n) time, which improves upon the O(nk) runtime of using the classic Gale--Shapley stable matching algorithm when k is large. Finally, we provide experimental results on road networks for these algorithms and a heuristic algorithm that performs better than the Gale--Shapley algorithm for any range of values of k.

A square-contact representation of a planar graph $G=(V,E)$ maps vertices in $V$ to interior-disjoint axis-aligned squares in the plane and edges in $E$ to adjacencies between the sides of the corresponding squares. In this paper, we study proper square-contact representations of planar graphs, in which any two squares are either disjoint or share infinitely many points. We characterize the partial $2$-trees and the triconnected cycle-trees allowing for such representations. For partial $2$-trees our characterization uses a simple forbidden subgraph whose structure forces a separating triangle in any embedding. For the triconnected cycle-trees, a subclass of the triconnected simply-nested graphs, we use a new structural decomposition for the graphs in this family, which may be of independent interest. Finally, we study square-contact representations of general triconnected simply-nested graphs with respect to their outerplanarity index.

We show that, for any graph optimization problem in which the feasible solutions can be expressed by a formula in monadic second-order logic describing sets of vertices or edges and in which the goal is to minimize the sum of the weights in the selected sets, we can find the $k$ best solutions for $n$-vertex graphs of bounded treewidth in time $\mathcal O(n+k\log n)$. In particular, this applies to the problem of finding the $k$ shortest simple paths between given vertices in directed graphs of bounded treewidth, giving an exponential speedup in the per-path cost over previous algorithms.

We introduce new dynamic set intersection data structures, which we call 2-3 cuckoo filters and hash tables. These structures differ from the standard cuckoo hash tables and cuckoo filters in that they choose two out of three locations to store each item, instead of one out of two, ensuring that any item in an intersection of two structures will have at least one common location in both structures. We demonstrate the utility of these structures by using them in improved algorithms for listing triangles and answering set intersection queries in internal or external memory. For a graph G of n vertices and m edges, our internal-memory triangle listing algorithm runs in O(m⌈(α(G)log w)/w⌉ + k) expected time, where α(G) is the arboricity of G, w is the number of bits in a machine word, and k is the number of output triangles. Our external-memory algorithm uses O(sort(n,α(G))+ sort(m⌈(α(G)log w)/w⌉) + sort(k)) expected number of I/Os.

We use multi-level parallelism and a new type of data structures, known as 2-3 cuckoo filters, to answer set intersection queries faster than previous methods, with applications to improved sparse Boolean matrix multiplication.

We consider relations between the size, treewidth, and local crossing number (maximum number of crossings per edge) of graphs embedded on topological surfaces. We show that an $n$-vertex graph embedded on a surface of genus $g$ with at most $k$ crossings per edge has treewidth $O(\sqrt{(g+1)(k+1)n})$ and layered treewidth $O((g+1)k)$ and that these bounds are tight up to a constant factor. In the special case of $g=0$, so-called $k$-planar graphs, the treewidth bound is $O(\sqrt{(k+1)n})$, which is tight and improves upon a known $O((k+1)^{3/4}n^{1/2})$ bound. Analogous results are proved for map graphs defined with respect to any surface. Finally, we show that for $g

We study various versions of the problem of scheduling platoons of autonomous vehicles through an unregulated intersection, where an algorithm must schedule which platoons should wait so that others can go through, so as to minimize the maximum delay for any vehicle. We provide polynomial-time algorithms for constructing such schedules for a k-way merge intersection, for constant k, and for a crossing intersection involving two-way traffic. We also show that the more general problem of scheduling autonomous platoons through an intersection that includes both a k-way merge, for non-constant k, and a crossing of two-way traffic is NP-complete.

For an undirected $n$-vertex graph $G$ with non-negative edge-weights, we consider the following type of query: given two vertices $s$ and $t$ in $G$, what is the weight of a minimum $st$-cut in $G$? We solve this problem in preprocessing time $O(n\log^3 n)$ for graphs of bounded genus, giving the first sub-quadratic time algorithm for this class of graphs. Our result also improves by a logarithmic factor a previous algorithm by Borradaile, Sankowski and Wulff-Nilsen (FOCS 2010) that applied only to planar graphs. Our algorithm constructs a Gomory-Hu tree for the given graph, providing a data structure with space $O(n)$ that can answer minimum-cut queries in constant time. The dependence on the genus of the input graph in our preprocessing time is $2^{O(g^2)}$.

We define treetopes, a generalization of the three-dimensional roofless polyhedra (Halin graphs) to arbitrary dimensions. Like roofless polyhedra, treetopes have a designated base facet such that every face of dimension greater than one intersects the base in more than one point. We prove an equivalent characterization of the 4-treetopes using the concept of clustered planarity from graph drawing, and we use this characterization to recognize the graphs of 4-treetopes in polynomial time. This result provides one of the first classes of 4-polytopes, other than pyramids and stacked polytopes, that can be recognized efficiently from their graphs.

Consider a sequence s_1,...,s_n of points in the plane. We want to find all maximal subsequences with a given hereditary property P: find for all indices i the largest index j^*(i) such that s_i,...,s_{j^*(i)} has property P. We provide a general methodology that leads to the following specific results: - In O(n log^2 n) time we can find all maximal subsequences with diameter at most 1. - In O(n log n loglog n) time we can find all maximal subsequences whose convex hull has area at most 1. - In O(n) time we can find all maximal subsequences that define monotone paths in some (subpath-dependent) direction. The same methodology works for graph planarity, as follows. Consider a sequence of edges e_1,...,e_n over a vertex set V. In O(n log n) time we can find, for all indices i, the largest index j^*(i) such that (V,{e_i,..., e_{j^*(i)}}) is planar.

We consider relations between the size, treewidth, and local crossing number (maximum number of crossings per edge) of graphs embedded on topological surfaces. We show that an n-vertex graph embedded on a surface of genus g with at most k crossings per edge has treewidth $$O(\sqrt{(g+1)(k+1)n})$$ and layered treewidth $$O((g+1)k)$$ , and that these bounds are tight up to a constant factor. As a special case, the k-planar graphs with n vertices have treewidth $$O(\sqrt{(k+1)n})$$ and layered treewidth $$O(k+1)$$ , which are tight bounds that improve a previously known $$O((k+1)^{3/4}n^{1/2})$$ treewidth bound. Additionally, we show that for $$g

We introduce the study of forcing sets in mathematical origami. The origami material folds flat along straight line segments called creases, each of which is assigned a folding direction of mountain or valley. A subset F of creases is forcing if the global folding mountain/valley assignment can be deduced from its restriction to F. In this paper we focus on one particular class of foldable patterns called Miura-ori, which divide the plane into congruent parallelograms using horizontal lines and zigzag vertical lines. We develop efficient algorithms for constructing a minimum forcing set of a Miura-ori map, and for deciding whether a given set of creases is forcing or not. We also provide tight bounds on the size of a forcing set, establishing that the standard mountain-valley assignment for the Miura-ori is the one that requires the most creases in its forcing sets. Additionally, given a partial mountain/valley assignment to a subset of creases of a Miura-ori map, we determine whether the assignment domain can be extended to a locally flat-foldable pattern on all the creases. At the heart of our results is a novel correspondence between flat-foldable Miura-ori maps and 3-colorings of grid graphs.

We use three-dimensional hyperbolic geometry to define a form of power diagram for systems of circles in the plane that is invariant under Möbius transformations. By applying this construction to circle packings derived from the Koebe–Andreev–Thurston circle packing theorem, we show that every planar graph of maximum degree three has a planar Lombardi drawing (a drawing in which the edges are drawn as circular arcs, meeting at equal angles at each vertex). We use circle packing to construct planar Lombardi drawings of a special class of 4-regular planar graphs, the medial graphs of polyhedral graphs, and we show that not every 4-regular planar graph has a planar Lombardi drawing. We also use these power diagrams to characterize the graphs formed by two-dimensional soap bubble clusters (in equilibrium configurations) as being exactly the 3-regular bridgeless planar multigraphs, and we show that soap bubble clusters in stable equilibria must in addition be 3-connected.

Associating the regions of a geographic subdivision with the cells of a grid is a basic operation that is used in various types of maps, like spatially ordered treemaps and OD maps. In these cases the regular shapes of the grid cells allows easy representation of extra information about the regions. The main challenge is to find an association that allows a user to find a region in the grid quickly. We call the representation of a set of regions as a grid a grid map.

We characterize the graphs formed by two-dimensional soap bubbles as being exactly the 3-regular bridgeless planar multigraphs. Our characterization combines a local characterization of soap bubble graphs in terms of the curvatures of arcs meeting at common vertices, a proof that this characterization remains invariant under Mobius transformations, an application of Mobius invariance to prove bridgelessness, and a Mobius-invariant power diagram of circles previously developed by the author for applications in graph drawing.

We consider the problem of analyzing social network data sets in which the edges of the network have timestamps, and we wish to analyze the subgraphs formed from edges in contiguous subintervals of these timestamps. We provide data structures for these problems that use near-linear preprocessing time, linear space, and sublogarithmic query time to handle queries that ask for the number of connected components, number of components that contain cycles, number of vertices whose degree equals or is at most some predetermined value, number of vertices that can be reached from a starting set of vertices by time-increasing paths, and related queries.

This paper presents a new sampling method for motion planning that can generate configurations more uniformly distributed on C-obstacle surfaces than prior approaches. Here, roadmap nodes are generated from the intersections between C-obstacles and a set of uniformly distributed fixed-length segments in C-space. The results show that this new sampling method yields samples that are more uniformly distributed than previous obstacle-based methods such as OBPRM, Gaussian sampling, and Bridge test sampling. UOBPRM is shown to have nodes more uniformly distributed near C-obstacle surfaces and also requires the fewest nodes and edges to solve challenging motion planning problems with varying narrow passages.

A rectangular layout is a partition of a rectangle into a finite set of interior-disjoint rectangles. These layouts are used as rectangular cartograms in cartography, as floorplans in building architecture and VLSI design, and as graph drawings. Often areas are associated with the rectangles of a rectangular layout and it is desirable for one rectangular layout to represent several area assignments. A layout is area-universal if any assignment of areas to rectangles can be realized by a combinatorially equivalent rectangular layout. We identify a simple necessary and sufficient condition for a rectangular layout to be area-universal: a rectangular layout is area-universal if and only if it is one-sided. We also investigate similar questions for perimeter assignments. The adjacency requirements for the rectangles of a rectangular layout can be specified in various ways, most commonly via the dual graph of the layout. We show how to find an area-universal layout for a given set of adjacency requirements whenever such a layout exists. Furthermore we show how to impose restrictions on the orientations of edges and junctions of the rectangular layout. Such an orientation-constrained layout, if it exists, may be constructed in polynomial time, and all orientation-constrained layouts may be listed in polynomial time per layout.

We study the combinatorial complexity of D-dimensional polyhedra defined as the intersection of n halfspaces, with the property that the highest dimension of any bounded face is much smaller than D. We show that, if d is the maximum dimension of a bounded face, then the number of vertices of the polyhedron is O(nd) and the total number of bounded faces of the polyhedron is O(nd 2). For inputs in general position the number of bounded faces is O(nd). For any fixed d, we show how to compute the set of all vertices, how to determine the maximum dimension of a bounded face of the polyhedron, and how to compute the set of bounded faces in polynomial time, by solving a polynomial number of linear programs.

We describe a synopsis structure, the Difference Digest, that allows two nodes to compute the elements belonging to the set difference in a single round with communication overhead proportional to the size of the difference times the logarithm of the keyspace. While set reconciliation can be done efficiently using logs, logs require overhead for every update and scale poorly when multiple users are to be reconciled. By contrast, our abstraction assumes no prior context and is useful in networking and distributed systems applications such as trading blocks in a peer-to-peer network, and synchronizing link-state databases after a partition.

We describe a method for performing greedy geometric routing for any n-vertex simple connected graph G in the hyperbolic plane, so that a message M between any pair of vertices may be routed by having each vertex that receives M pass it to a neighbor that is closer to M's destination. Our algorithm produces succinct embeddings, where vertex positions are represented using O(\log n) bits and distance comparisons may be performed efficiently using these representations. These properties are useful, for example, for routing in sensor networks, where storage and bandwidth are limited.

In this paper, we study the straggler identification problem, in which an algorithm must determine the identities of the remaining members of a set after it has had a large number of insertion and deletion operations performed on it, and now has relatively few remaining members. The goal is to do this in o(n) space, where n is the total number of identities. Straggler identification has applications, for example, in determining the unacknowledged packets in a high-bandwidth multicast data stream. We provide a deterministic solution to the straggler identification problem that uses only O(d log n) bits, based on a novel application of Newton's identities for symmetric polynomials. This solution can identify any subset of d stragglers from a set of n O(log n)-bit identifiers, assuming that there are no false deletions of identities not already in the set. Indeed, we give a lower bound argument that shows that any small-space deterministic solution to the straggler identification problem cannot be guaranteed to handle false deletions. Nevertheless, we provide a simple randomized solution, using O(d log n log (1/∈)) bits that can maintain a multiset and solve the straggler identification problem, tolerating false deletions, where ∈ > 0 is a user-defined parameter bounding the probability of an incorrect response. This randomized solution is based on a new type of Bloom filter, which we call the invertible Bloom filter.

We define a simple orthogonal polyhedron to be a three-dimensional polyhedron with the topology of a sphere in which three mutually-perpendicular edges meet at each vertex. By analogy to Steinitz's theorem characterizing the graphs of convex polyhedra, we characterize the graphs of simple orthogonal polyhedra: they are exactly the 3-regular bipartite planar graphs in which the removal of any two vertices produces at most two connected components. We also characterize two subclasses of these polyhedra: corner polyhedra, which can be drawn by isometric projection in the plane with only one hidden vertex, and xyz polyhedra, in which each axis-parallel line through a vertex contains exactly one other vertex. Based on our characterizations we find efficient algorithms for constructing orthogonal polyhedra from their graphs

We give efficient data-oblivious algorithms for several fundamental geometric problems that are relevant to geographic information systems, including planar convex hulls and all-nearest neighbors. Our methods are "data-oblivious" in that they don't perform any data-dependent operations, with the exception of operations performed inside low-level blackbox circuits having a constant number of inputs and outputs. Thus, an adversary who observes the control flow of one of our algorithms, but who cannot see the inputs and outputs to the blackbox circuits, cannot learn anything about the input or output. This behavior makes our methods applicable to secure multiparty computation (SMC) protocols for geographic data used in location-based services. In SMC protocols, multiple parties wish to perform a computation on their combined data without revealing individual data to the other parties. For instance, our methods can be used to solve a problem posed by Du and Atallah, where Alice has a set, A, of m private points in the plane, Bob has another set, B, of n private points in the plane, and Alice and Bob want to jointly compute the convex hull of A ∪ B without disclosing any more information than what can be derived from the answer. In particular, neither Alice nor Bob want to reveal any of their respective points that are in the interior of the convex hull of A ∪ B.

This paper considers pairs of optimization problems that are defined from a single input and for which it is desired to find a good approximation to either one of the problems. In many instances, it is possible to efficiently find an approximation of this type that is better than known inapproximability lower bounds for either of the two individual optimization problems forming the pair. In particular, we find either a (1 + ∊)-approximation to (1, 2)-TSP or a 1/∊-approximation to maximum independent set, from a given graph, in linear time. We show a similar paired approximation result for finding either a coloring or a long path. However, no such tradeoff exists in some other cases: for set cover and hitting set problems defined from a single set family, and for clique and independent set problems on the same graph, it is not possible to find an approximation when both problems are combined that is better than the best approximation for either problem on its own.

We provide linear-time algorithms for geometric graphs with sublinearly many edge crossings. That is, we provide algorithms running in $O(n)$ time on connected geometric graphs having n vertices and k pairwise crossings, where k is smaller than n by an iterated logarithmic factor. Specific problems that we study include Voronoi diagrams and single-source shortest paths. Our algorithms all run in linear time in the standard comparison-based computational model; hence, we make no assumptions about the distribution or bit complexities of edge weights, nor do we utilize unusual bit-level operations on memory words. Instead, our algorithms are based on a planarization method that “zeros in” on edge crossings, together with methods for applying planar separator decompositions to geometric graphs with sublinearly many crossings. Incidentally, our planarization algorithm also solves an open computational geometry problem of Chazelle for triangulating a self-intersecting polygonal chain having n segments and k crossings in linear time, for the case when k is sublinear in n by an iterated logarithmic factor.

Squaregraphs were originally defined as finite plane graphs in which all inner faces are quadrilaterals (i.e., 4-cycles) and all inner vertices (i.e., the vertices not incident with the outer face) have degrees larger than three. The planar dual of a finite squaregraph is determined by a triangle-free chord diagram of the unit disk, which could alternatively be viewed as a triangle-free line arrangement in the hyperbolic plane. This representation carries over to infinite plane graphs with finite vertex degrees in which the balls are finite squaregraphs. Algebraically, finite squaregraphs are median graphs for which the duals are finite circular split systems. Hence squaregraphs are at the crosspoint of two dualities, an algebraic one and a geometric one, and thus lend themselves to several combinatorial interpretations and structural characterizations. With these and the 5-colorability theorem for circle graphs at hand, we prove that every squaregraph can be isometrically embedded into the Cartesian product of five trees. This embedding result can also be extended to the infinite case without reference to an embedding in the plane and without any cardinality restriction when formulated for median graphs free of cubes and further finite obstructions. Further, we exhibit a class of squaregraphs that can be embedded into the product of three trees, and we characterize those squaregraphs that are embeddable into the product of just two trees. Finally, finite squaregraphs enjoy a number of algorithmic features that do not extend to arbitrary median graphs. For instance, we show that minimum-size median-generating sets of finite squaregraphs can be computed in polynomial time, whereas, not unexpectedly, the corresponding problem for median graphs turns out to be NP-hard. Finite squaregraphs can be recognized in linear time by a Breadth-First-Search.

A two-site distance function defines a "distance" measure from a point to a pair of points; mathematically, it is a mapping D:R2×(R2×R2)R+. A Voronoi diagram for a two-site distance function D and a set S of planar point sites has a region V (p, q) for each pair of sites p,q-S , where V(p,q) is defined as the set of all points in the plane "closer" to (p, q)"under distance function D"than to any other pair of sites in S. Two-site distance functions and their Voronoi diagrams have been explored by Barequet et al. (2002) and animated by Barequet et al. (2001), who give

A rectangular layout is a partition of a rectangle into a finite set of interior-disjoint rectangles. They are used as rectangular cartograms in cartography, as floorplans in building architecture and VLSI design, and as graph drawings. Often areas are associated with the rectangles of a rectangular layout and it is desirable for one rectangular layout to represent several area assignments. A layout is area-universal if any assignment of areas to rectangles can be realized by a combinatorially equivalent rectangular layout. We identify a simple necessary and sufficient condition for a rectangular layout to be area-universal: a rectangular layout is area-universal if and only if it is one-sided. We also investigate similar questions for perimeter assignments. The adjacency requirements for the rectangles of a rectangular layout can be specified in various ways, most commonly via the dual graph of the layout. We show how to find an area-universal layout for a given set of adjacency requirements whenever such a layout exists.

A geometric graph is a graph embedded in the plane with vertices at points and edges drawn as curves (which are usually straight line segments) between those points. The average transversal complexity of a geometric graph is the number of edges of that graph that are crossed by random line or line segment.

We provide linear-time algorithms for geometric graphs with sublinearly many crossings. That is, we provide algorithms running in O(n) time on connected geometric graphs having n vertices and k crossings, where k is smaller than n by an iterated logarithmic factor. Specific problems we study include Voronoi diagrams and single-source shortest paths. Our algorithms all run in linear time in the standard comparison-based computational model; hence, we make no assumptions about the distribution or bit complexities of edge weights, nor do we utilize unusual bit-level operations on memory words. Instead, our algorithms are based on a planarization method that “zeroes in” on edge crossings, together with methods for extending planar separator decompositions to geometric graphs with sublinearly many crossings. Incidentally, our planarization algorithm also solves an open computational geometry problem of Chazelle for triangulating a self-intersecting polygonal chain having n segments and k crossings in linear time, for the case when k is sublinear in n by an iterated logarithmic factor.

Let S be a surface embedded in space in such a way that each point has a neighborhood within which the surface is a terrain. Then S projects to an immersed surface in the plane, the boundary of which is a (possibly self-intersecting) curve. Under what circumstances can we reverse these mappings algorithmically? Shor and van Wyk considered one such problem, determining whether a curve is the boundary of an immersed disk; they showed that the self-overlapping curves defined in this way can be recognized in polynomial time. We show that several related problems are more difficult: it is NP-complete to determine whether an immersed disk is the projection of a disk embedded in space, or whether a curve is the boundary of an immersed surface in the plane that is not constrained to be a disk. However, when a casing is supplied with a self-intersecting curve, describing which component of the curve lies above and which below at each crossing, we may determine in time linear in the number of crossings whether the cased curve forms the projected boundary of a surface in space. As a related result, we show that an immersed surface with a single boundary curve that crosses itself n times has at most 2n/2 combinatorially distinct spatial embeddings, and we discuss the existence of fixed-parameter tractable algorithms for related problems.

Abstract We present a graph algorithm to find fundamental cycles aligned with the principal curvature directions of a surface. Specifically, we use the tree‐cotree decomposition of graphs embedded in manifolds, guided with edge weights, in order to produce these cycles. Our algorithm is very quick compared to existing methods, with a worst case running time ofO(nlogn+gn) wherenis the number of faces andgis the surface genus. Further, its flexibility to accommodate different weighting functions and to handle boundaries may be used to produce cycles suitable for a variety of applications and models.

We show how to test the bipartiteness of an intersection graph of n line segments or simple polygons in the plane, or of an intersection graph of balls in d -dimensional Euclidean space, in time O ( n log n ). More generally, we find subquadratic algorithms for connectivity and bipartiteness testing of intersection graphs of a broad class of geometric objects. Our algorithms for these problems return either a bipartition of the input or an odd cycle in its intersection graph. We also consider lower bounds for connectivity and k -colorability problems of geometric intersection graphs. For unit balls in d dimensions, connectivity testing has equivalent randomized complexity to construction of Euclidean minimum spanning trees, and for line segments in the plane connectivity testing has the same lower bounds as Hopcroft's point-line incidence testing problem; therefore, for these problems, connectivity is unlikely to be solved as efficiently as bipartiteness. For line segments or planar disks, testing k -colorability of intersection graphs for k > 2 is NP-complete.

We provide efficient constant-factor approximation algorithms for the problems of finding a hierarchical clustering of a point set in any metric space, minimizing the sum of minimimum spanning tree lengths within each cluster, and in the hyperbolic or Euclidean planes, minimizing the sum of cluster perimeters. Our algorithms for the hyperbolic and Euclidean planes can also be used to provide a pants decomposition , that is, a set of disjoint simple closed curves partitioning the plane minus the input points into subsets with exactly three boundary components, with approximately minimum total length. In the Euclidean case, these curves are squares; in the hyperbolic case, they combine our Euclidean square pants decomposition with our tree clustering method for general metric spaces.

We describe algorithms, based on Avis and Fukuda's reverse search paradigm, for listing all maximal independent sets in a sparse graph in polynomial time and delay per output. For bounded degree graphs, our algorithms take constant time per set generated; for minor-closed graph families, the time is O ( n ) per set, and for more general sparse graph families we achieve subquadratic time per set. We also describe new data structures for maintaining a dynamic vertex set S in a sparse or minor-closed graph family, and querying the number of vertices not dominated by S ; for minor-closed graph families the time per update is constant, while it is sublinear for any sparse graph family. We can also maintain a dynamic vertex set in an arbitrary m -edge graph and test the independence of the maintained set in time O (√m) per update. We use the domination data structures as part of our enumeration algorithms.

This paper studies real-world road networks from an algorithmic perspective, focusing on empirical studies that yield useful properties of road networks that can be exploited in the design of fast algorithms that deal with geographic data. Unlike previous approaches, our study is not based on the assumption that road networks are planar graphs. Indeed, based on the a number of experiments we have performed on the road networks of the 50 United States and District of Columbia, we provide strong empirical evidence that road networks are quite non-planar. Our approach therefore instead is directed at finding algorithmically-motivated properties of road networks as non-planar geometric graphs, focusing on alternative properties of road networks that can still lead to efficient algorithms for such problems as shortest paths and Voronoi diagrams. In particular, we study road networks as multiscale-dispersed graphs, which is a concept we formalize in terms of disk neighborhood systems. This approach allows us to develop fast algorithms for road networks without making any additional assumptions about the distribution of edge weights. In fact, our algorithms can allow for non-metric weights.

We study approximate topological matching of quadrilateral meshes, that is, the problem of finding as large a set as possible of matching portions of two quadrilateral meshes. This study is motivated by applications in graphics that involve shape modeling whose results need to be merged in order to produce a final unified representation of an object. We show that the problem of producing a maximum approximate topological match of two quad meshes in NP-hard. Given this result, which makes an exact solution extremely unlikely, we show that the natural greedy algorithm derived from polynomial-time graph isomorphism can produce poor results, even when it is possible to find matches with only a few non-matching quads. Nevertheless, we provide a "lazy-greedy" algorithm that is guaranteed to find good matches when mis-matching portions of mesh are localized. Finally, we provide empirical evidence that this approach produces good matches between similar quad meshes.

Abstract We describe algorithms for canonically partitioning semi‐regular quadrilateral meshes into structured submeshes, using an adaptation of the geometric motorcycle graph of Eppstein and Erickson to quad meshes. Our partitions may be used to efficiently find isomorphisms between quad meshes. In addition, they may be used as a highly compressed representation of the original mesh. These partitions can be constructed in sublinear time from a list of the extraordinary vertices in a mesh. We also study the problem of further reducing the number of submeshes in our partitions—we prove that optimizing this number is NP‐hard, but it can be efficiently approximated.

We show that the triangulations of a finite point set form a flip graph that can be embedded isometrically into a hypercube, if and only if the point set has no empty convex pentagon. Point sets of this type include intersections of lattices with convex sets, points on two lines, and several other infinite families. As a consequence, flip distance in such point sets can be computed efficiently.

We consider the problem of placing a small number of angle guards inside a simple polygon P so asto provide efficient proofs that any given point is inside P. Each angle guard views an infinite wedge of the plane, and a point can prove membership in P if it is inside the wedges for a set of guards whose common intersection contains no points outside the polygon. This model leads to a broad class of new art gallery type problems, which we call "sculpture garden" problems and for which we provide upper and lower bounds. In particular, we show there is a polygon P such that a "natural" angle-guard vertex placement cannot fully distinguish between pointson the inside and outside of P (even if we place a guard at every vertex of P), which implies that Steiner-point guards are sometimes necessary. More generally, we show that, for any polygon P, there is a set of n+2(h-1) angle guards that solve the sculpture garden problem for P, where h is the number of holes in P (so a simple polygon can be defined with n-2 guards). In addition, we show that, for any orthogonal polygon P, the sculpture garden problem can besolved using n/2 angle guards. We also give an example of a class of simple (non-general-position) polygons that have sculpture garden solutions using O(√n) guards, and we show this bound is optimal to within a constant factor. Finally, while optimizing the number of guards solving a sculpture garden problem for a particular P is of unknown complexity, we show how to find in polynomial time a guard placement whose size is within a factor of 2 of the optimal number for any particular polygon.

We study practically efficient methods for performing combinatorial group testing. We present efficient nonadaptive and two‐stage combinatorial group testing algorithms, which identify the at most d items out of a given set of n items that are defective, using fewer tests for all practical set sizes. For example, our two‐stage algorithm matches the information‐theoretic lower bound for the number of tests in a combinatorial group testing regimen.

We present memory-efficient deterministic algorithms for constructing ϵ-nets and ϵ-approximations of streams of geometric data. Unlike probabilistic approaches, these deterministic samples provide guaranteed bounds on their approximation factors. We show how our deterministic samples can be used to answer approximate online iceberg geometric queries on data streams. We use these techniques to approximate several robust statistics of geometric data streams, including Tukey depth, simplicial depth, regression depth, the Thiel-Sen estimator, and the least median of squares. Our algorithms use only a polylogarithmic amount of memory, provided the desired approximation factors are at least inverse-polylogarithmic. We also include a lower bound for noniceberg geometric queries.

No abstract available.

Due to decreasing transistor sizes and increasing clock frequency, interconnect delay is a dominant factor in achieving timing closure in deep-submicrometer designs. In field programmable gate arrays (FPGA), interconnect delay is contributed by programmable routing switches. This increases the wire delay significantly. In FPGA devices, the interconnect delay is usually more than 40% of the total delay. Techniques like wire pipelining and retiming can manage delay of timing critical wires. However, the latency of the design limits the total pipelining in the design. Therefore, new techniques are needed at synthesis stage to consider the effect of critical wires in the design. In this paper, we propose an intuitive Critical Edge Reduction (CER) algorithm, which minimizes the number of critical wires on a maximal delay- budgeting solution under fixed latency constraint. We prove that this problem is NP-hard. We provide an integer linear programming formulation of the problem and an iterative heuristic algorithm (CER). During the course of our algorithm, we introduce multiple graph problems. We give a proof of NP-hardness of one such problem, which we call max arc-cost balancing problem. In our experiments, we present an in-depth analysis of tradeoff between various maximal budgetings and critical edge minimization. We implemented our design flow using a set of MediaBench datapaths on Xilinx VirtexE FPGA devices. Using our algorithm, the Xilinx Place-and-Route tool achieved timing closure, which is, on average, 2.8 times faster than using maximum budgeting. The resulting average clock period using CER algorithm outperforms the one using the maximum budgeting by 6%. Other results show similar advantages of critical edge minimization over traditional budgeting techniques.

We consider a class of multivariate recurrences frequently arising in the worst-case analysis of Davis-Putnam-style exponential-time backtracking algorithms for NP-hard problems. We describe a technique for proving asymptotic upper bounds on these recurrences, by using a suitable weight function to reduce the problem to that of solving univariate linear recurrences; show how to use quasiconvex programming to determine the weight function yielding the smallest upper bound; and prove that the resulting upper bounds are within a polynomial factor of the true asymptotics of the recurrence. We develop and implement a multiple-gradient descent algorithm for the resulting quasiconvex programs, using a real-number arithmetic package for guaranteed accuracy of the computed worst-case time bounds.

We present a new multi-dimensional data structure, which we call the skip quadtree (for point data in R2) or the skip octree (for point data in Rd, with constant d > 2). Our data structure combines the best features of two well-known data structures, in that it has the well-defined "box"-shaped regions of region quadtrees and the logarithmic-height search and update hierarchical structure of skip lists. Indeed, the bottom level of our structure is exactly a region quadtree (or octree for higher dimensional data). We describe efficient algorithms for inserting and deleting points in a skip quadtree, as well as fast methods for performing point location, approximate range, and approximate nearest neighbor queries.

The dilation of a Euclidean graph is defined as the ratio of distance in the graph divided by distance in Rd. In this paper we consider the problem of positioning the root of a star such that the dilation of the resulting star is minimal. We present a deterministic O(n log n)-time algorithm for evaluating the dilation of a given star; a randomized O(n log n) expected-time algorithm for finding an optimal center in Rd; and for the case d = 2, a randomized O(n2α(n) log2n) expected-time algorithm for finding an optimal center among the input points.

We present a framework for designing efficient distributed data structures for multi-dimensional data. Our structures, which we call skip-webs, extend and improve previous randomized distributed data structures, including skipnets and skip graphs. Our framework applies to a general class of data querying scenarios, which include linear (one-dimensional) data, such as sorted sets, as well as multi-dimensional data, such as d-dimensional octrees and digital tries of character strings defined over a fixed alphabet.We show how to perform a query over such a set of n items spread among n hosts using O(log n/log log n) messages for one-dimensional data, or O(log n) messages for fixed-dimensional data, while using only O(log n) space per host. We also show how to make such structures dynamic so as to allow for insertions and deletions in O(log n) messages for quadtrees, octrees, and digital tries, and O(log n/log log n) messages for one-dimensional data. Finally, we show how to apply a blocking strategy to skip-webs to further improve message complexity for one-dimensional data when hosts can store more data.

We present memory-efficient deterministic algorithms for constructing ∈-nets and ∈-approximations of streams of geometric data. Unlike probabilistic approaches, these deterministic samples provide guaranteed bounds on their approximation factors. We show how our deterministic samples can be used to answer approximate online iceberg geometric queries on data streams. We use these techniques to approximate several robust statistics of geometric data streams, including Tukey depth, simplicial depth, regression depth, the Thiel-Sen estimator, and the least median of squares. Our algorithms use only a polylogarithmic amount of memory, provided the desired approximation factors are inverse-polylogarithmic. We also include a lower bound for non-iceberg geometric queries.

We prove that the geometric thickness of graphs whose maximum degree is no more than four is two. All of our algorithms run in O(n) time, where n is the number of vertices in the graph. In our proofs, we present an embedding algorithm for graphs with maximum degree three that uses an n x n grid and a more complex algorithm for embedding a graph with maximum degree four. We also show a variation using orthogonal edges for maximum degree four graphs that also uses an n x n grid. The results have implications in graph theory, graph drawing, and VLSI design.

This video illustrates a new method for subdividing the surface of a triangulated 3d polyhedron, without changing the geometry of the model, so that the triangles of the subdivided mesh can be ordered into a single triangle strip. Our method guarantees that the subdivided mesh has at most 3/2 the original number of triangles, and in practice performs much better. Our strips can be used not only for efficient rendering, but also for other applications including the generation of space filling curves.

In this paper we study the problem of how resilient networks are to node faults. Specifically, we investigate the question of how many faults a network can sustain so that it still contains a large (i.e. linear-sized) connected component that still has approximately the same expansion as the original fault-free network. For this we apply a pruning technique which culls away parts of the faulty network which have poor expansion. This technique can be applied to both adversarial faults and to random faults. For adversarial faults we prove that for every network with expansion α, a large connected component with basically the same expansion as the original network exists for up to a constant times α • n faults. This result is tight in the sense that every graph G of size n and uniform expansion α (•),i.e. G has an expansion of α (n) and every subgraph G' of size m of G has an expansion of O (α (m)), can be broken into sublinear components with w(α (n) • n) faults.For random faults we observe that the situation is significantly different. In this case the expansion of a graph only gives a very weak bound on its resilience to random faults. Specifically, there are networks of uniform expansion O(≾n) that are resilient against a constant fault probability but there are also networks of uniform expansion Ω(1/log n) that are not resilient against a O(1/log n) fault probability. Thus, a different parameter is needed. For this we introduce the span of a graph which allows us to determine the maximum fault probability in a much better way than the expansion can. We use the span to show the first known results for the effect of random faults on the expansion of d-dimensional meshes.

Abstract Triangle strips have been widely used for efficient rendering. It is NP‐complete to test whether a given triangulated model can be represented as a single triangle strip, so many heuristics have been proposed to partition models into few long strips. In this paper, we present a new algorithm for creating a single triangle loop or strip from a triangulated model. Our method applies a dual graph matching algorithm to partition the mesh into cycles, and then merges pairs of cycles by splitting adjacent triangles when necessary. New vertices are introduced at midpoints of edges and the new triangles thus formed are coplanar with their parent triangles, hence the visual fidelity of the geometry is not changed. We prove that the increase in the number of triangles due to this splitting is 50% in the worst case, however for all models we tested the increase was less than 2%. We also prove tight bounds on the number of triangles needed for a single‐strip representation of a model with holes on its boundary. Our strips can be used not only for efficient rendering, but also for other applications including the generation of space filling curves on a manifold of any arbitrary topology. Categories and Subject Descriptors (according to ACM CCS): I.3.5 [Computer Graphics]: Geometric algorithms, Triangulation, Stripification. G.2.2 [Graph algorithms]: Hamiltonian Path, Hamiltonian Cycle, Perfect Matching.

We consider the problem of finding a large color space that can be generated by all units in multi-projector tiled display systems. Viewing the problem geometrically as one of finding a large parallelepiped within the intersection of multiple parallelepipeds, and using colorimetric principles to define a volume-based objective function for comparing feasible solutions, we develop an algorithm for finding the optimal gamut in time O(n3), where n denotes the number of projectors in the system. We also discuss more efficient quasiconvex programming algorithms for alternative objective functions based on maximizing the quality of the color space extrema.

We introduce a class of "inverse parametric optimization" problems, in which one is given both a parametric optimization problem and a desired optimal solution; the task is to determine parameter values that lead to the given solution. We describe algorithms for solving such problems for minimum spanning trees, shortest paths, and other "optimal subgraph" problems and discuss applications in multicast routing, vehicle path planning, resource allocation, and board game programming.

We present an algorithm to unfold any triangulated 2-manifold (in particular, any simplicial polyhedron) into a non-overlap-linebreak ping, connected planar layout in linear time. The manifold is cut only along its edges. The resulting layout is connected, but it may have a disconnected interior; the triangles are connected at vertices, but not necessarily joined along edges. We extend our algorithm to establish a similar result for simplicial manifolds of arbitrary dimension.

This correspondence analyzes the distribution of loop lengths in graphical models for turbo decoding. The properties of such loops are of significant interest in the context of iterative decoding algorithms based on belief propagation. We estimate the probability that there exist no loops of length less than or equal to c at a randomly chosen node in the acyclic directed graphical (ADC) model for turbo decoding, using a combination of counting arguments and approximations. When K, the number of information bits, is large, this probability is approximately e -2/sup c-1/-4/K, for c/spl ges/4, where nodes for input information bits are ignored for convenience. The analytical results are validated by simulations. For example, for turbo codes with K=64,000, a randomly chosen node has a less than 1% chance of being on a loop of length less than or equal to 10, but has a greater than 99.9% chance of being on a loop of length less than or equal to 20.

The regression depth of a hyperplane with respect to a set of n points in R d is the minimum number of points the hyperplane must pass through in a rotation to vertical. We generalize hyperplane regression depth to k-flats for any k between 0 and d - 1. The k = 0 case gives the classical notion of center points. We prove that for any k and d, deep k-flats exist, that is, for any set of n points there always exists a k-flat with depth at least a constant fraction of n. As a consequence, we derive a linear-time (1 + #)-approximation algorithm for the deepest flat. 1. INTRODUCTION Linear regression asks for an affine subspace (a flat) that fits a set of data points. The most familiar case assumes d-1 independent or explanatory variables and one dependent or response variable, and fits a hyperplane to explain the dependent variable as a linear function of the independent variables. Quite often, however, there may be more than one dependent variable, and the multivariate regression p...

We show how to use a combination of tree-clustering techniques and computational geometry to improve the time bounds for optimal pivot selection in the primal network simplex algorithm for minimum-cost flow and related problems and for pivot execution in the dual network simplex algorithm, from O(m) to \documentclass{article}\pagestyle{empty}\begin{document}$0(\sqrt{m})$\end{document} per pivot. Our techniques can also speed up network simplex algorithms for generalized flow, shortest paths with negative edges, maximum flow, the assignment problem, and the transshipment problem. © 2000 John Wiley & Sons, Inc.

We introduce a class of "inverse parametric optimization" problems, in which one is given both a parametric optimization problem and a desired optimal solution; the task is to determine parameter values that lead to the given solution. We describe algorithms for solving such problems for minimum spanning trees, shortest paths, and other "optimal subgraph" problems, and discuss applications in multicast routing, vehicle path planning, resource allocation, and board game programming.

Article Free Access Share on Raising roofs, crashing cycles, and playing pool: applications of a data structure for finding pairwise interactions Authors: David Eppstein Department of Information and Computer Science, University of California, Irvine, CA Department of Information and Computer Science, University of California, Irvine, CAView Profile , Jeff Erickson Center for Geometric Computing, Department of Computer Science, Duke University, Box 90129, Durham, NC Center for Geometric Computing, Department of Computer Science, Duke University, Box 90129, Durham, NCView Profile Authors Info & Claims SCG '98: Proceedings of the fourteenth annual symposium on Computational geometryJune 1998 Pages 58–67https://doi.org/10.1145/276884.276891Published:07 June 1998Publication History 27citation318DownloadsMetricsTotal Citations27Total Downloads318Last 12 Months52Last 6 weeks13 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

We consider the parametric minimum spanning tree problem, in which we are given a graph with edge weights that are linear functions of a parameter /spl lambda/ and wish to compute the sequence of minimum spanning trees generated as /spl lambda/ varies. We also consider the kinetic minimum spanning tree problem, in which /spl lambda/ represents time and the graph is subject in addition to changes such as edge insertions, deletions, and modifications of the weight functions as time progresses. We solve both problems in time O(n/sup 2/3/log/sup 4/3/) per combinatorial change in the tree (or randomized O(n/sup 2/3/log/sup 4/3/ n) per change). Our time bounds reduce to O(n/sup 1/2/log/sup 3/2/ n) per change (O(n/sup 1/2/log n) randomized) for planar graphs or other minor-closed families of graphs, and O(n/sup 1/4/log/sup 3/2/ n) per change (O(n/sup 1/4/ log n) randomized) for planar graphs with weight changes but no insertions or deletions.

A three-dimensional polygon is triangulable if it has a non-self-intersecting triangulation which defines a simply-connected 2-manifold. We show that the problem of deciding whether a 3-dimensional polygon is triangulable is NP-complete. We then establish some necessary conditions and some sufficient conditions for a polygon to be triangulable, providing special cases when the decision problem may be answered in polynomial time.

We give algorithms for finding the k shortest paths (not required to be simple) connecting a pair of vertices in a digraph. Our algorithms output an implicit representation of these paths in a digraph with n vertices and m edges, in time O(m + n log n + k). We can also find the k shortest paths from a given source s to each vertex in the graph, in total time O(m + n log n + kn). We describe applications to dynamic programming problems including the knapsack problem, sequence alignment, maximum inscribed polygons, and genealogical relationship discovery.

We consider the problem of maintaining a dynamic planar graph subject to edge insertions and edge deletions that preserve planarity but that can change the embedding. We describe algorithms and data structures for maintaining information about 2- and 3-vertex-connectivity, and 3- and 4-edge-connectivity in a planar graph in O(n 1/2 ) amortized time per insertion, deletion, or connectivity query. All of the data structures handle insertions that keep the graph planar without regard to any particular embedding of the graph. Our algorithms are based on a new type of sparsification combined with several properties of separators in planar graphs.

We provide data strutures that maintain a graph as edges are inserted and deleted, and keep track of the following properties with the following times: minimum spanning forests, graph connectivity, graph 2-edge connectivity, and bipartiteness in time O ( n 1/2 ) per change; 3-edge connectivity, in time O ( n 2/3 ) per change; 4-edge connectivity, in time O ( n α( n )) per change; k -edge connectivity for constant k , in time O ( n log n ) per change;2-vertex connectivity, and 3-vertex connectivity, in the O ( n ) per change; and 4-vertex connectivity, in time O ( n α( n )) per change. Further results speed up the insertion times to match the bounds of known partially dynamic algorithms. All our algorithms are based on a new technique that transforms an algorithm for sparse graphs into one that will work on any graph, which we call sparsification.

A three-dimensional polygon is triangulable if it has a non-self-intersecting triangulation which defines a simply-connected 2-manifold. We show that the problem of deciding whether a 3D polygon is triangulable is an NP-complete problem. We then establish some necessary conditions and some sufficient conditions for a polygon to be triangulable, providing special cases when the decision problem may be answered in polynomial time. We also discuss optimal triangulations of 3D polygons. Keywords: three-dimensions, triangulation. 1 Introduction A 3-dimensional polygon is a closed chain of straight segments, where every two successive segments share exactly one point and the intersection of every non-successive pair of segments is empty. A triangulation of a 3-dimensional Work on this paper by the first author has been supported by the Israeli Ministry of Science and the Arts, Eshkol Grant 0562-1-94. Work by the second author has been supported by the funds of the National Science Founda...

We show that any polyhedron forming a topological ball with an even number of quadrilateral sides can be partitioned into O(n) topological cubes, meeting face to face. The result generalizes to non-simply-connected polyhedra satisfying an additional bipartiteness condition. The same techniques can also be used to reduce the geometric version of the hexahedral mesh generation problem to a finite case analysis amenable to machine solution.

We describe algorithms and data structures for maintaining a dynamic planar graph subject to edge insertions and edge deletions that preserve planarity but that can change the embedding. We give a fully dynamic planarity testing algorithm that maintains a graph subject to edge insertions and deletions and that allows queries that test whether the graph is currently planar, or whether a potential new edge would violate planarity, inO(n1/2) amortized time per update or query. We give fully dynamic algorithms for maintaining the connected components, the best swap and the minimum spanning forest of a planar graph inO(log n) worst-case time per insertion andO(log2 n) per deletion. Finally, we give fully dynamic algorithms for maintaining the 2-edge-connected components of a planar graph inO(log n) amortized time per insertion andO(log2 n) per deletion. All of the data structures, except for the one that answers planarity queries, handle only insertions that keep the graph planar. All our algorithms improve previous bounds. The improvements are based upon a new type of sparsification combined with several properties of separators in planar graphs.

Patterns used for supersampling in graphics have been analyzed from statistical and signal-processing viewpoints. We present an analysis based on a type of isotropic discrepancy—how good patterns are at estimating the area in a region of defined type. We present algorithms for computing discrepancy relative to regions that are defined by rectangles, halfplanes, and higher-dimensional figures. Experimental evidence shows that popular supersampling patterns have discrepancies with better asymptotic behavior than random sampling, which is not inconsistent with theoretical bounds on discrepancy.

We consider worst case time bounds for NP-complete problems including 3-coloring, 3-edge-coloring, and 3-list-coloring. Our algorithms are based on a common generalization of these problems, called symbol-system satisfiability or, briefly, SSS. 3-SAT is equivalent to (2,3)-SSS while the other problems above are special cases of (3,2)-SSS; there is also a natural duality transformation from (a,b)-SSS to (b,a)-SSS. We give a fast algorithm for (3,2)-SSS and use it to improve the time bounds for solving the other problems listed above.

We relate the sequence of minimum bases of a matroid with linearly varying weights to three problems from combinatorial geometry: k-sets, lower envelopes of line segments, and convex polygons in line arrangements.Using these relations we show new lower bounds on the number of base changes in such sequences: Q(nr1i3) for a general n-element matroid with rank r, and Q(rmr(n)) for the special case of parametric graph minimum spanning trees.The only previous lower bound was fl(n log r) for uniform matroids; upper bounds of 0(rmz1i2) for arbitrary matroids and 0(mn112/ log* n) for uniform matroids were also known.

We give a deterministic linear time algorithm for finding a “good” sphere separator of a k-ply neighborhood system Φ in any fixed dimension, where a k-ply neighborhood system in $\IR$ d is a collection of n balls such that no points in the space is c

We give algorithms for finding the k shortest paths (not required to be simple) connecting a pair of vertices in a digraph. Our algorithms output an implicit representation of these paths in a digraph with n vertices and m edges, in time O(m+n log n+k). We can also find the k shortest paths from a given source s to each vertex in the graph, in total time O(m+n log n+kn). We describe applications to dynamic programming problems including the knapsack problem, sequence alignment, and maximum inscribed polygons.>

We consider graphs such as the minimum spanning tree, minimum Steiner tree, minimum matching, and traveling salesman tour for n points in the d-dimensional unit cube. For each of these graphs, we show that the worst-case sum of the dth powers of edge lengths is O(log n). This is a consequence of a general "gap theorem": for any subadditive geometric graph, either the worst-case sum of edge lengths is O(n (d-1)/d ) and the sum of dth powers is O(log n), or the sum of edge lengths is #(n). We look more closely at some specific graphs: the worst-case sum of dth powers is O(1) for minimum matching, but #(log n) for traveling salesman tour, which answers a question of Snyder and Steele. 1. Introduction A worst-case, or a priori , bound on a geometric graph is a bound that depends only on the assumption that all vertices lie within a given container. Such a bound does not depend on the specific locations of vertices, nor on any probabilistic assumptions. Early papers especially ...

We describe a practical and provably good algorithm for approximating center points in any number of dimensions. Here c is a center point of a point set P in ℝd if every closed halfspace containing c contains at least |P|/(d+1) points of P. Our algorithm has a small constant factor and is the first approximate center point algorithm whose complexity is subexponential in d. Moreover, it can be optimally parallelized to require O(log2 d loglog n) time. Our algorithm has been used in mesh partitioning methods, and has the potential to improve results in practice for constructing weak ε-nets and other geometric algorithms. We derive a variant of our algorithm with a time bound fully polynomial in d, and show how to combine our approach with previous techniques to compute high quality center points more quickly.

We develop algorithms for computing the discrepancy of point sets in various Euclidean range spaces.

We give a deterministic linear time algorithm for finding a small cost sphere separator of a k-ply neighborhood system Φ in any fixed dimension, where a k-ply neighborhood system in Rd is a collection of n balls such that no points in the space is covered by more than k balls. The sphere separator intersects at most O (k1/2 nd-1/d) balls of Φ and it divides the remaining of Φ into two parts: those in the interior and those in the exterior of the sphere, respectively, so that the larger part contains at most δn balls (d+1/d+2 < δ < 1). This result improves the O(n2) time deterministic algorithm of Miller and Teng [29] and answers a major algorithmic open question posed by Mille, Teng,Thurston and Vavasis [23,25].

Article Free Access Share on Separator based sparsification for dynamic planar graph algorithms Authors: David Eppstein View Profile , Zvi Galil View Profile , Giuseppe F. Italiano View Profile , Thomas H. Spencer View Profile Authors Info & Claims STOC '93: Proceedings of the twenty-fifth annual ACM symposium on Theory of ComputingJune 1993 Pages 208–217https://doi.org/10.1145/167088.167159Published:01 June 1993Publication History 23citation582DownloadsMetricsTotal Citations23Total Downloads582Last 12 Months25Last 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

We show how to triangulate polygonal regions---adding extra vertices as necessary--- with triangles of guaranteed quality. Using only O(n) triangles, we can guarantee that the smallest height (shortest dimension) of a triangle in a triangulation of an n-vertex polygon (with holes) is a constant fraction of the largest possible. For simple polygons, using O(n log n) triangles, we can guarantee that the largest angle is no greater than 150 ffi . This bound increases to O(n 3=2 ) triangles for the case of polygons with holes. We can add the guarantee on smallest height to these no-large-angle results, without increasing the asymptotic complexity of the triangulation. Finally we give a nonobtuse triangulation algorithm for convex polygons that uses O(n 1:85 ) triangles. Keywords: Computational geometry, mesh generation, triangulation, angle condition. 1. Introduction There have been a number of recent papers on the general problem of triangulating a planar point set or pol...

The authors describe dynamic data structures for half-space range reporting and for maintaining the minima of a decomposable function. Using these data structures, they obtain efficient dynamic algorithms for a number of geometric problems, including closest/farthest neighbor searching, fixed dimension linear programming, bi-chromatic closest pair, diameter, and Euclidean minimum spanning tree.>

The authors provide data structures that maintain a graph as edges are inserted and deleted, and keep track of the following properties: minimum spanning forests, best swap, graph connectivity, and graph 2-edge-connectivity, in time O(n/sup 1/2/log(m/n)) per change; 3-edge-connectivity, in time O(n/sup 2/3/) per change; 4-edge-connectivity, in time O(n alpha (n)) per change; k-edge-connectivity, in time O(n log n) per change; bipartiteness, 2-vertex-connectivity, and 3-vertex-connectivity, in time O(n log(m/n)) per change; and 4-vertex-connectivity, in time O(n log(m/n)+n alpha (n)) per change. Further results speed up the insertion times to match the bounds of known partially dynamic algorithms. The algorithms are based on a technique that transforms algorithms for sparse graphs into ones that work on any graph, which they call sparsification.>

We perform linear programming optimizations on the intersection of k polyhedra in R 3 , represented by their outer recursive decompositions, in expected time O(k log k log n + √k log k log 3 n). We use this result to derive efficient algorithms for dynamic linear programming problems in which constraints are inserted and deleted, and queries must optimize specified objective functions. As an application, we describe an improved solution to the planar 2-center problem. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

Dynamic programming solutions to a number of different recurrence equations for sequence comparison and for RNA secondary structure prediction are considered. These recurrences are defined over a number of points that is quadratic in the input size; however only a sparse set matters for the result. Efficient algorithms for these problems are given, when the weight functions used in the recurrences are taken to be linear. The time complexity of the algorithms depends almost linearly on the number of points that need to be considered; when the problems are sparse this results in a substantial speed-up over known algorithms.

Dynamic programming solutions to two recurrence equations, used to compute a sequence alignment from a set of matching fragments between two strings, and to predict RNA secondary structure, are considered. These recurrences are defined over a number of points that is quadratic in the input size; however, only a sparse set matters for the result. Efficient algorithms are given for solving these problems, when the cost of a gap in the alignment or a loop in the secondary structure is taken as a convex or concave function of the gap or loop length. The time complexity of our algorithms depends almost linearly on the number of points that need to be considered; when the problems are sparse, this results in a substantial speed-up over known algorithms.

We describe methods for triangulating polygonal re-

Linear programming optimizations on the intersection of k polyhedra in R/sup 3/, represented by their outer recursive decompositions, are performed in expected time O(k log k log n+ square root k log k log/sup 3/ n). This result is used to derive efficient algorithms for dynamic linear programming problems ill which constraints are inserted and deleted, and queries must optimize specified objective functions. As an application, an improved solution to the planar 2-center problem, is described.>

Several versions of the problem of generating triangular meshes for finite-element methods are studied. It is shown how to triangulate a planar point set or a polygonally bounded domain with triangles of bounded aspect ratio, how to triangulate a planar point set with triangles having no obtuse angles, how to triangulate a point set in arbitrary dimension with simplices of bounded aspect ratio, and how to produce a linear-size Delaunay triangulation of a multidimensional point set by adding a linear number of extra points. All the triangulations have size within a constant factor of optimal and run in optimal time O(n log n+k) with input of size n and output of size k. No previous work on mesh generation simultaneously guarantees well-shaped elements and small total size.>

Natarajan reduced the problem of designing a certain type of mechanical parts orienter to that of finding reset sequences for monotonic deterministic finite automata. He gave algorithms that in polynomial time either find such sequences or prove that no such sequence exists. In this paper a new algorithm based on breadth-first search is presented that runs in faster asymptotic time than Natarajan’s algorithms, and in addition finds the shortest possible reset sequence if such a sequence exists. Tight bounds on the length of the minimum reset sequence are given. The time and space bounds of another algorithm given by Natarajan are further improved.That algorithm finds reset sequences for arbitrary deterministicfinite automata when all states are initially possible.

A number of important computational problems in molecular biology, geology, speech recognition, and other areas can be expressed as recurrences which have typically been solved with dynamic programming. By using more sophisticated data structures, and by taking advantage of further structure from the applications, the authors speed up the computation of several of these recurrences by one or two orders of magnitude. The algorithms used are simple and practical.>