Integration of combinatorial decompositions in the presence of collinearities

Many results in Combinatorial Integral Geometry are derived by integration of the combinatorial decompositions associated with finite point sets {P _i } given in the plane ?². However, most previous cases of integration of the decompositions in question were carried out for the point sets {P _i } containing no triads of collinear points, where the familiar algorithm sometimes called the “Four indicator formula” can be used. The present paper is to demonstrate that the complete combinatorial algorithm valid for sets {P _i } not subject to the mentioned restriction opens the path to various results, including the field of Stochastic Geometry. In the paper the complete algorithm is applied first in an integration procedure in a study of the perforated convex domains, i.e convex domains containing a finite array of non-overlapping convex holes. The second application is in the study of random colorings of the plane that are Euclidean motions invariant in distribution, basing on the theory of random polygonal windows from the so-called Independent Angles (IA) class. The method is a direct averaging of the complete combinatorial decompositions written for colorings observed in polygonal windows from the IA class. The approach seems to be quite general, but promises to be especially effective for the random coloring generated by random Poisson polygon process governed by the Haar measure on the group of Euclidean motions of the plane, assuming that a point P ∈ ?² is colored J if P is covered by exactly J polygons of the Poisson process. A general theorem clearing the way for Laplace transform treatment of the random colorings induced on line segments is formulated.     

Computing Cartograms with Optimal Complexity

In a rectilinear dual of a planar graph vertices are represented by simple rectilinear polygons, while edges are represented by side-contact between the corresponding polygons. A rectilinear dual is called a cartogram if the area of each region is equal to a pre-specified weight. The complexity of a cartogram is determined by the maximum number of corners (or sides) required for any polygon. In a series of papers the polygonal complexity of such representations for maximal planar graphs has been reduced from the initial 40 to 34, then to 12 and very recently to the currently best known 10. Here we describe a construction with 8-sided polygons, which is optimal in terms of polygonal complexity as 8-sided polygons are sometimes necessary. Specifically, we show how to compute the combinatorial structure and how to refine it into an area-universal rectangular layout in linear time. The exact cartogram can be computed from the area-universal layout with numerical iteration, or can be approximated with a hill-climbing heuristic. We also describe an alternative construction of cartograms for Hamiltonian maximal planar graphs, which allows us to directly compute the cartograms in linear time. Moreover, we prove that even for Hamiltonian graphs 8-sided rectilinear polygons are necessary, by constructing a non-trivial lower bound example. The complexity of the cartograms can be reduced to 6 if the Hamiltonian path has the extra property that it is one-legged, as in outer-planar graphs. Thus, we have optimal representations (in terms of both polygonal complexity and running time) for Hamiltonian maximal planar and maximal outer-planar graphs. Finally we address the problem of constructing small-complexity cartograms for 4-connected graphs (which are Hamiltonian). We first disprove a conjecture, posed by two set of authors, that any 4-connected maximal planar graph has a one-legged Hamiltonian cycle, thereby invalidating an attempt to achieve a polygonal complexity 6 in cartograms for this graph class. We also prove that it is NP-hard to decide whether a given 4-connected plane graph admits a cartogram with respect to a given weight function.     

Optimal System of Loops on an Orientable Surface

Every compact orientable boundaryless surface M can be cut along simple loops with a common point v₀, pairwise disjoint except at v₀, so that the resulting surface is a topological disk; such a set of loops is called a {\it system of loops} for M. The resulting disk may be viewed as a polygon in which the sides are pairwise identified on the surface; it is called a polygonal schema. Assuming that M is a combinatorial surface, and that each edge has a given length, we are interested in a shortest (or optimal) system of loops homotopic to a given one, drawn on the vertex-edge graph of M. We prove that each loop of such an optimal system is a shortest loop among all simple loops in its homotopy class. We give an algorithm to build such a system, which has polynomial running time if the lengths of the edges are uniform. As a byproduct, we get an algorithm with the same running time to compute a shortest simple loop homotopic to a given simple loop.     

Visibility Queries and Maintenance in Simple Polygons

Abstract. In this paper we explore some novel aspects of visibility for stationary and moving points inside a simple polygon P . We provide a mechanism for expressing the visibility polygon from a point as the disjoint union of logarithmically many canonical pieces using a quadratic-space data structure. This allows us to report visibility polygons in time proportional to their size, but without the cubic space overhead of earlier methods. The same canonical decomposition can be used to determine visibility within a frustum, or to compute various attributes of the visibility polygon efficiently. By exploring the connection between visibility polygons and shortest-path trees, we obtain a kinetic algorithm that can track the visibility polygon as the viewpoint moves along polygonal paths inside P , at a polylogarithmic cost per combinatorial change in the visibility or in the flight plan of the point. The combination of the static and kinetic algorithms leads to a new static algorithm in which we can trade off space for increased overhead in the query time. As another application, we obtain an algorithm which computes the weak visibility polygon from a query segment inside P in output-sensitive time.     

Locked and Unlocked Polygonal Chains in Three Dimensions

This paper studies movements of polygonal chains in three dimensions whose links are not allowed to cross or change length. Our main result is an algorithmic proof that any simple closed chain that initially takes the form of a planar polygon can be made convex in three dimensions. Other results include an algorithm for straightening open chains having a simple orthogonal projection onto some plane, and an algorithm for making convex any open chain initially configured on the surface of a polytope. All our algorithms require only O(n) basic ``moves.' Received October 9, 1999, and in revised form February 6, 2001, and April 26, 2001. Online publication August 28, 2001.     

The first gap for total curvatures of planar graphs with nonnegative curvature

We prove that the total curvature of a planar graph with nonnegative combinatorial curvature is at least 1/12 if it is positive. Moreover, we classify the metric structures of ambient polygonal surfaces for planar graphs attaining this bound.     

Generalized Pleijel identity

A family of identities primarily associated with isoperimetric inequalities for planar convex domains was discovered by Pleijel in 1956. We call these identities classical Pleijel identities. R. V. Ambartzumian gave combinatorial proof of these identities and pointed out that they can be applied to find chord length distribution functions for convex domains. In the classical Pleijel identities integration is over the measure in the space \(\mathbb{G}\) of lines which is invariant with respect to the all Euclidean motions. In the present paper they are considered for any locally-finite measure in the space \(\mathbb{G}\). These identities are applied to find the so-called orientation-dependent chord length distribution (or density) functions for bounded convex domains.     

The Geodesic Diameter of Polygonal Domains

This paper studies the geodesic diameter of polygonal domains having $h$ h holes and $n$ n corners. For simple polygons (i.e., $h=0$ h = 0 ), the geodesic diameter is determined by a pair of corners of a given polygon and can be computed in linear time, as shown by Hershberger and Suri. For general polygonal domains with $h \ge 1$ h ≥ 1 , however, no algorithm for computing the geodesic diameter was known prior to this paper. In this paper, we present the first algorithms that compute the geodesic diameter of a given polygonal domain in worst-case time $O(n^{7.73})$ O ( n 7.73 ) or $O(n^7 (\log n + h))$ O ( n 7 ( log n + h ) ) . The main difficulty unlike the simple polygon case relies on the following observation revealed in this paper: two interior points can determine the geodesic diameter and in that case there exist at least five distinct shortest paths between the two.     

Construction of the Solvability Set in Differential Games with Simple Motion and Nonconvex Terminal Set

We consider planar zero-sum differential games with simple motion, fixed terminal time, and polygonal terminal set. The geometric constraint on the control of each player is a convex polygonal set or a line segment. In the case of a convex terminal set, an explicit formula is known for the solvability set (a level set of the value function, maximal u-stable bridge, viability set). The algorithm corresponding to this formula is based on the set operations of algebraic sum and geometric difference (the Minkowski difference). We propose an algorithm for the exact construction of the solvability set in the case of a nonconvex polygonal terminal set. The algorithm does not involve the additional partition of the time interval and the recovery of intermediate solvability sets at additional instants. A list of half-spaces in the three-dimensional space of time and state coordinates is formed and processed by a finite recursion. The list is based on the polygonal terminal set with the use of normals to the polygonal constraints on the controls of the players.     

Approximating the Fréchet Distance for Realistic Curves in Near Linear Time

We present a simple and practical (1+ε)-approximation algorithm for the Fréchet distance between two polygonal curves in ? ^d . To analyze this algorithm we introduce a new realistic family of curves, c-packed curves, that is closed under simplification. We believe the notion of c-packed curves to be of independent interest. We show that our algorithm has near linear running time for c-packed polygonal curves, and similar results for other input models, such as low-density polygonal curves.     

Identification of a small reliable and efficient set of consistent scenarios

In scenario analyses, in which experts have rated the consistency of impact factor levels, all scenarios are defined by vectors of these impact factors. Because the identification of scenarios out of all combinatorial scenarios was time consuming and inefficient, three new approaches were developed: Local efficiency as a goal function of a simple combinatorial optimisation, a multidimensional distance indicator for sets, and a small and efficient selection algorithm. The methods are illustrated and tested on a large scenario analysis from an ETH-UNS case study. Their convergent validity is shown by the comparison of the selected scenarios.     

Chord calculus and stochastic geometry

Chord calculus is a collection of integration procedures applied to to the combinatorial decompositions that give the solution of the Buffon-Sylvester problem for n needles in a plane or the similar problem in IR ³. It is a source of various integral geometry identities, some of which find their application in Stochastic geometry. In the present paper these applications are focused on random convex polygons and polyhedrons, where we define certain classes where rather simple tomography analysis is possible. The choice of these classes (the Independent Angles class and the Independent Orientations class) is due to the nature of the results of the Chord calculus. The last section points at an application of the convex polygons from the Independent Angles class to Boolean sets in the plane (Boolean models) whose probability distibutions are invariant with respect to the group of Euclidean motions of the plane.     

Coalescence of synchronous couplings

 We consider a pair of reflected Brownian motions in a Lipschitz planar domain starting from different points but driven by the same Brownian motion. First we construct such a pair of processes in a certain weak sense, since it is not known whether a strong solution to the Skorohod equation in Lipschitz domains exists. Then we prove that the distance between the two processes converges to zero with probability one if the domain has a polygonal boundary or it is a ``lip domain', i.e., a domain between the graphs of two Lipschitz functions with Lipschitz constants strictly less than 1. Received: 2 March 2001 / Revised version: 6 March 2001 / Published online: 1 July 2002     

Construction of a maximal stable bridge in games with simple motions on the plane

It is known that the solvability set (the maximal stable bridge) in a zero-sum differential game with simple motions, fixed terminal time, geometric constraints on the controls of the first and second players, and convex terminal set can be constructed by means of a program absorption operator. In this case, a backward procedure for the construction of t-sections of the solvability set does not need any additional partition times. We establish the same property for a game with simple motions, polygonal terminal set (which is generally nonconvex), and polygonal constraints on the players’ controls on the plane. In the particular case of a convex terminal set, the operator used in the paper coincides with the program absorption operator.     

Expected runtimes of a simple evolutionary algorithm for the multi-objective minimum spanning tree problem

Evolutionary algorithms are applied to problems that are not well understood as well as to problems in combinatorial optimization. The analysis of these search heuristics has been started for some well-known polynomial solvable problems. Such analyses are starting points for the analysis of evolutionary algorithms on difficult problems. We present the first runtime analysis of a multi-objective evolutionary algorithm on a NP-hard problem. The subject of our analysis is the multi-objective minimum spanning tree problem for which we give upper bounds on the expected time until a simple evolutionary algorithm has produced a population including for each extremal point of the Pareto front a corresponding spanning tree. These points are of particular interest as they give a 2-approximation of the Pareto front. We show that in expected pseudopolynomial time a population is produced that includes for each extremal point a corresponding spanning tree.     

Asymptotics of convex lattice polygonal lines with a constrained number of vertices

A detailed combinatorial analysis of planar convex lattice polygonal lines is presented. This makes it possible to answer an open question of Vershik regarding the existence of a limit shape when the number of vertices is constrained.     

A Middle School Extension of Pick's Theorem to Areas of Nonsimple Closed Polygonal Regions

The author has extended Pick's theorem for simple closed polygonal regions to unions of simple closed polygonal regions–a topic that is manageable for middle grade students. From sets of data including numbers of boundary points and numbers of interior points, students are guided to discover Pick's theorem. Additionally, with the author's creation of crossing points, Pick's theorem is extended to include areas of other polygonal regions. The article is developed along lines of the 1989 Standards of the NCTM in the use of data tables which lead to the discovery of a formula.     

Link distance and shortest path problems in the plane

This paper describes algorithms to compute Voronoi diagrams, shortest path maps, the Hausdorff distance, and the Fréchet distance in the plane with polygonal obstacles. The underlying distance measures for these algorithms are either shortest path distances or link distances. The link distance between a pair of points is the minimum number of edges needed to connect the two points with a polygonal path that avoids a set of obstacles. The motivation for minimizing the number of edges on a path comes from robotic motions and wireless communications because turns are more difficult in these settings than straight movements.Link-based Voronoi diagrams are different from traditional Voronoi diagrams because a query point in the interior of a Voronoi face can have multiple nearest sites. Our site-based Voronoi diagram ensures that all points in a face have the same set of nearest sites. Our distance-based Voronoi diagram ensures that all points in a face have the same distance to a nearest site.The shortest path maps in this paper support queries from any source point on a fixed line segment. This is a middle-ground approach because traditional shortest path maps typically support queries from either a fixed point or from all possible points in the plane.The Hausdorff distance and Fréchet distance are fundamental similarity metrics for shape matching. This paper shows how to compute new variations of these metrics using shortest paths or link-based paths that avoid polygonal obstacles in the plane.     

A new greedy algorithm for the quadratic assignment problem

The classical greedy algorithm for discrete optimization problems where the optimal solution is a maximal independent subset of a finite ground set of weighted elements, can be defined in two ways which are dual to each other. The Greedy-In where a solution is constructed from the empty set by adding the next best element, one at a time, until we reach infeasibility, and the Greedy-Out where starting from the ground set we delete the next worst element, one at a time, until feasibility is reached. It is known that while the former provides an approximation ratio for maximization problems, its worst case performance is not bounded for minimization problems, and vice-versa for the later. However the Greedy-Out algorithm requires an oracle for checking the existence of a maximal independent subset which for most discrete optimization problems is a difficult task. In this work we present a Greedy-Out algorithm for the quadratic assignment problem by providing a combinatorial characterization of its solutions.     

Finding efficient solutions for rectilinear distance location problems efficiently

Given n planar existing facility locations, a planar new facility location X is called efficient if there is no other location Y for which the rectilinear distance between Y and each existing facility is at least as small as between X and each existing facility, and strictly less for at least one existing facility. Rectilinear distances are typically used to measure travel distances between points via rectilinear aisles or street networks. We first present a simple arrow algorithm, based entirely on geometrical analysis, that constructs all efficient locations. We then present a row algorithm which is of order n(log n) that constructs all efficient locations, and establish that no alternative algorithm can be of a lower order.