EuroCG 2012

Abstract: In this paper we study the most-demanding predicate for computing the Euclidean Voronoi diagram of axes-aligned line segments, namely the Incircle predicate. In particular, we show that the Incircle predicate can be answered by evaluating the signs of algebraic expressions of degree at most 6; this is half the algebraic degree we get when we evaluate the Incircle predicate using the current state-of-the-art approach.

Abstract: We present an algorithm that approximates the medial axis of a manifold in R³ given by a sufficiently dense point sample. The resulting, non-discrete approximation converges to the medial axis as the sampling density approaches infinity and we establish a homotopy between the canonical parameterizations of both structures. While there is no subquadratic upper bound on the output complexity of previous algorithms for non-discrete medial axis approximation, the output of our algorithm is guaranteed to be of linear size. The algorithm is (arguably) simpler than previous approaches and practically efficient.

Abstract: Let f(n,k) be the minimum number of edges that must be removed from a complete geometric graph G on n points, so that there exists a tree on k vertices that is no longer a planar subgraph of G. In this paper we show that ( [1/2] )[(n²)/(k−1)]−[n/2] ≤ f(n,k) ≤ 2 [(n(n−2))/(k−2)]−n. For the case when k=n, we show that 2 ≤ f(n,n) ≤ 3. For the case when k=n and G is a geometric graph on a set of points in convex position, we show that at least three edges must be removed.

Abstract: Given an arrangement of lines in the plane, what is the minimum number c of colors required to color the lines so that no cell of the arrangement is monochromatic? In this paper we give bounds on the number c, as well as some of its variations. We cast these problems as characterizing the chromatic and the independence numbers of a new family of geometric hypergraphs.

Abstract: This paper presents an algorithm for generating new tiling patterns in which three streams of tiles cross without overlap or gaps. For given three tiles, their copies are placed in three different directions, gradually changing their shapes so that they cross at the center. The algorithm is based on periodic tiling of hexagons, morphing between two tiles, and mixing of two or more curves. The proposed method might give a new direction of extension of tiling art started by M. C. Escher.

Abstract: In this paper we investigate the following type of proximity problems: given a set of n points in the plane P = {p₁, p₂, p₃, . . ., p_n}, for each point p_i find a pair {p_j, p_k}, where i ≠ j, k,such that a measure M defined on the triplet of points {p_i, p_j, p_k} is maximized or minimized. The cases where M is the distance from p_i to the segment or line defined by {p_j, p_k} have been extensively studied. We study the cases where M is the sum, product or the difference of the distances from p_i to the points p_j and p_k; the area, perimeter of the triangle defined by p_i, p_j and p_k, as well as the radius of the circumcircle defined by them. We also revisit the problem for the line-distance measure.

Abstract: A constant-work-space algorithm has read-only access to an input array and may use only O(1) additional words of O(logn) bits, where n is the input size.We show how to triangulate a plane straight-line graph with n vertices in O(n²) time and constant work-space. We also consider the problem of preprocessing a simplen-gon P for shortest path queries, where P given by the ordered sequence of its vertices. For this, we relax the space constraint to allow s words of work-space. After quadratic preprocessing, the shortest path between any two points inside P can be found in O(n²/s) time.

Abstract: Let G be a cycle-free connected straight-line graph with predefined edge lengths and fixed order of incident edges around each vertex. We address the problem of deciding whether there exists a simple polygon P such that G is the straight skeleton of P. We show that for given G such a polygon P might not exist, and if it exists it might not be unique. For small star graphs and caterpillars we give necessary and sufficient conditions for constructing P.

Abstract: The Erdös-Szekeres theorem states that, for every k, there is a number n_k such that every set of n_k points in general position in the plane contains a subset of k points in convex position. If we ask the same question for subsets whose convex hull does not contain any other point from the set, this is not true: as shown by Horton, there are sets of arbitrary size that do not contain an empty 7-gon. These questions have also been studied extensively from a computational point of view, and polynomial time algorithms for finding the largest (empty) convex set have been given for the planar case. In higher dimension, it is not known how to compute such a set efficiently. In this paper, we show that already in 3 dimensions no polynomial time algorithm exists for determining the largest (empty) convex set (unless P=NP), by proving that the corresponding decision problem is NP-hard. This answers a question by Dobkin, Edelsbrunner and Overmars from 1990. As a corollary, we derive a similar result for the closely related problem of testing weak eps-nets in R³. Answering a question by Chazelle et al. from 1995, our reduction shows that the problem is co-NP-hard. Finally, we make several suggestions for further research on the subject.

Abstract: Let P be a d-dimensional n-point set. A Tverberg-partition of P is a partition of P into r sets P₁, ..., P_r such that the convex hulls ch(P₁), ...,ch(P_r) have non-empty intersection. A point in the intersection of the ch(P_i) is called a Tverberg point of depth r for P. A classic result by Tverberg implies that there always exists a Tverberg partition of size n/(d+1), but it is not known how to find such a partition in polynomial time. Therefore, approximate solutions are of interest. We describe a deterministic algorithm that finds a Tverberg partition of size n/4(d+1)³ in time d^O(logd) n. This means that for every fixed dimension we can compute an approximate Tverberg point (and hence also an approximate center point)in linear time. Our algorithm is obtained by combining a novel lifting approach with a recent result by Miller and Sheehy.

Abstract: A grid drawing of a graph maps vertices to grid points and edges to line segments that avoid such points but the extremes. First, we determine the maximal number of grid points that must lie on a line segment of a grid drawing. This number is closely connected to the chromatic number. Second, we study how many columns we need to draw a graph in the grid, introducing some new NP-complete problems. Finally, we show that any planar graph has a planar grid drawing where every line segment contains exactly two grid points. This result proves conjectures asked by David Flores-Penaloza and Francisco Javier Zaragoza Martinez.

Abstract: We consider a variant of the Art Gallery Problem, where a polygonal region is to be covered with light sources that emit light fading with distance. We describe a practical approximation algorithm based on the simplex method and primal-dual LP separation. For the case where the light positions are given, we describe a fully polynomial-time approximation scheme.

Abstract: We consider the non-crossing connectors problem, which is stated as follows: Given n simply connected regions R₁,...,R_n in the plane and finite point sets P_i subset of R_i for i=1,...,n, are there non-crossing connectors y_i for (R_i,P_i), i.e., arc-connected sets y_i with P_i subset of y_i subset of R_i for every i=1,...,n such that y_i and y_j are disjoint for all i different from j? We prove that non-crossing connectors do always exist if the regions form a collection of pseudo-disks, i.e., the boundaries of every pair of regions intersect at most twice. We provide a simple polynomial-time algorithm if the regions are axis-aligned rectangles. Finally we prove that the general problem is NP-complete, even if the regions are convex, the boundaries of every pair of regions intersect at most four times and P_i consists of only two points on the boundary of R_i for i=1,...,n.

Abstract: We consider the problem of adding edges to a given graph in order to make it cubic (i.e., all vertices have degree 3). As a first result, we show that the problem is NP-complete if the resulting graph is required to be simple and planar. In the reduction, we rely on edges whose combinatorial embedding is not determined by the graph. Further, we show that the problem of deciding whether additional edges can be drawn on a given (embedded) plane geometric graph, in a way that the resulting plane geometric graph is cubic, is NP-complete. The problem remains NP-complete even if the initial graph is connected.

Abstract: Graph-theoretic properties of certain proximity graphs defined on planar point sets are investigated. We first consider some of the most common proximity graphs of the family of the Delaunay graph, and study their number of edges, minimum and maximum degree, clique number, and chromatic number. Then we focus on the higher order versions of some of these graphs and give bounds on the same properties.

Abstract: We consider a coloring problem on dynamic, one-dimensional point sets: points appearing and disappearing on a line at given times. We wish to color them with k colors so that at any time, any sequence of p(k) consecutive points, for some function p, contains at least one point of each color. We prove that no such function p(k) exists in general. However, in the restricted case in which points appear gradually, but never disappear, we give a coloring algorithm guaranteeing the property at any time with p(k)=8k−5. This can be interpreted as coloring point sets in R² with k colors such that any bottomless rectangle containing at least 8k−5 points contains at least one point of each color. Chen et al. (2009) proved that such colorings do not always exist in the case of general axis-aligned rectangles. Our result also complements recent contributions from Keszegh and Pálvölgyi (2011).

Abstract: We consider the maxmin length triangulation problem in polygons. We give an NP-hardness proof for the case of polygons with holes and interior points. For simple polygons we present an optimal algorithm using dynamic programming.

Abstract: We study the problem of finding non-crossing C-oriented paths that use as few links as possible and are homotopic to a set of input paths in an environment with C-oriented obstacles. We introduce a special type of C-oriented paths-smooth paths-and present a 2-approximation algorithm that runs in O(n² (n + logκ) + k_in logn) time, where n is the total number of paths and obstacle vertices, k_in is the total number of links in the input, and κ = |C|. The algorithm also computes an O(κ)-approximation for general C-oriented paths. As a related result we show that, given a set of (possibly crossing) C-oriented paths with a total of L links, non-crossing C-oriented paths homotopic to the input paths can require a total of Ω(L logκ) links.

Abstract: We give a lower bound of Ω(log(n/k)/loglog(n/k)) for the crossing number of shallow partitions in the plane

Abstract: Let P be a k-colored set of n points in general position on the plane, where k ≥ 2. A k-colored quadrangulation of P is a maximal straight-edge plane graph with vertex set P satisfying the property that every interior face is a properly colored quadrilateral, i.e., no edge connects vertices of the same color. It is easy to check that in general not every set of points admits a k-colored quadrangulation, and hence the use of extra points, known in the literature as Steiner points, is required in order to obtain one. In this paper, we show that if P satisfies some condition for the colors of the points in Conv(P), then a k-colored quadrangulation of P can always be constructed using less than [((16 k−2) n+7 k−2)/(39 k−6)] Steiner points. Our upper bound improves the previously known upper bound for k=3, and represents the first bounds for k ≥ 4.

Abstract: We prove that every oriented path with n vertices admits an upward planar embedding into every set of n²−n points in general position.

Abstract: We adapt the Goffin's Algorithm for construction of the Löwner-John ellipsoid for a full-dimensional zonotope given by the generator description.

Abstract: Let S be a subdivision of the plane into polygonal regions, where each region has an associated positive weight. The weighted region shortest path problem is to determine a shortest path in S between two points s,t ∈ S, where the distances are measured according to the weighted Euclidean metric - the length of a path is defined to be the weighted sum of (Euclidean) lengths of the subpaths within each region. We show that this problem cannot be solved in the Algebraic Computation Model over the Rational Numbers (ACMQ). The ACMQ can compute exactly any number that can be obtained from the rationals Q by applying a finite number of operations from +, −, ×, ÷, ^k√, for any integer k ≥ 2. Our proof uses Gröbner bases and Galois theory, and is based on Bajaj's technique.

Abstract: Let μ be a nice measure in R^d. A theorem of Yao and Yao states that R^d can be partitioned into 2^d parts of equal μ-measure such that every hyperplane avoids at least one element of the partition. We extend this result to the case when every hyperplane is required to avoid two elements of the partition, this can be done by partitioning R^d into 3 ·2^d−1 parts of equal μ-measure. Then we use this to obtain a result on a problem about the separation of points and hyperplanes.

Abstract: The motivation for this work comes from the digital mock-up process in car industry where constructions and motions in the design of a car are evaluated. One important task is to verify that moving components keep a given distance to other (stationary) components in their environment. The geometry of a component is described by a high quality triangle mesh and its trajectory is specified by a discrete sequence of positions and orientations. Solving this task, the basic operation is a triangle-triangle tolerance test:Given two triangles, determine whether their shortest distance is greater than a given tolerance value ε. A special case is the triangle-triangle intersection test choosing ε = 0. For the latter a lot of work has been done to solve it efficiently [2, 3, 4, 5]. We present efficient solutions for the generalized question. Our solutions are optimized for the treatment of millions of triangle-triangle tolerance tests in parallel on multi-core CPU and on the GPU.

Abstract: The orientation predicate is the core procedure in many important geometric algorithms, such as convex hull and triangulation computations. As the dimension of the computation space grows, a higher percentage of the computation time is consumed by these predicates. In this paper we study the computation of sequences of determinantal predicates in a signle or a sequence of convex hull computations. We propose a method that improves the amortized complexity of the determinants involved in a convex hull computation. Moreover, we study how can we use the computation done in a convex hull construction to improve the construction of subsequent convex hulls. Our two main tools are the dynamic determinant computation and the reusage of determinantal minors. Finally, we implement a simple method that optimizes the computation of subsequent determinantal predicates in both single and sequence of convex hull computations. The experiments show in the single convex hull scenario a speedup up to dimension 5 and in sequences of convex hulls a speedup of 100 times when the dimension is 6.

Abstract: We develop an incremental algorithm to compute the Newton polytope of the resultant, aka resultant polytope, or its projection along a given direction. Our algorithm exactly computes vertex- and halfspace-representations of the resultant polytope using an oracle producing resultant vertices in a given direction. It is output-sensitive as it uses one oracle call per vertex. We implement our algorithm using the experimental CGAL package triangulation. A variant of the algorithm computes successively tighter inner and outer approximations: when these polytopes have, respectively, 90% and 105% of the true volume, runtime is reduced up to 25 times. Compared to tropical geometry software, ours is faster up to dimensions 5 or 6, and competitive in higher dimensions. Compared to lrs, cdd, and polymake, the computation of convex hull is fastest along with polymake. The resultant is fundamental in algebraic elimination and in implicitizing parametric hypersurfaces: we compute the Newton polytope of surface equations in < 1sec, when there are < 100 terms in the parametric polynomials, which includes all common instances in geometric modeling. Our method computes instances of 5, 6 or 7-dimensional polytopes with 35K, 23K or 500 vertices, respectively, in < 2hr.

Abstract: Many geometric processing tasks can be performed efficiently on regular domains. As complex, non-convex, real-world geometries come into play, however, this efficiency is often lost and sometimes there may be no method to find a solution. Domain Mapping aims to construct some map from a geometrically complicated space to a simple, usually convex, space. Once this map is constructed, solutions can be found in the new target domain and transferred back to the original domain. Some problems that benefit from domain mapping include mesh construction, robot path planning and computer animation. This paper outlines a method to perform domain mapping using harmonic functions, following which an extension is presented that allows it to handle 2D domains containing voids.

Abstract: In this work we extend some well-known properties for simple line location - namely an incidence and a halving property - to a more general setting and use them to develop algorithms in order to approximate a set of n given points by one or more lines. This yields an O(n^4/3 logn) (O(n²)) algorithm for locating a single line minimizing the sum of (weighted) distances to the n points for point-line distances induced by a norm. A trimmed line which minimizes the sum of (weighted) distances to the m ≤ n closest of the n points can be found in O(n² logn) (O(n³)) time. Finally, K lines minimizing the sum of distances of each of the n points to the closest line is computed in O(n^2K+1 (K + logn)) time, where the logn factor only applies to the trimming case.

Abstract: We analyze the structural properties of the order-k Voronoi diagram of n line-segments. We show that order-k Voronoi regions may disconnect to Ω(n) faces. Nevertheless, the overall structural complexity of the order-k line-segment Voronoi diagram remains O(k(n−k)), similarly to its counterpart for points.

Abstract: Let S be a plane point set of n points with no three of them collinear and no four cocircular. Consider the circle passing through three points of S chosen uniformly at random and let X be the random variable that counts the number of points of S inside this circle. We show that expectation E_S(X) and variance V_S(X) of X only depend on the rectilinear crossing number cr(S) of S. More precisely, E_S(X) = [cr(S)/(n || 3)] + [(n−3)/4] and

VS(X) = (n−3)2 ⎛ ⎜ ⎝ cr(S) 8 ⎛ ⎝ n 4 ⎞ ⎠ − cr(S)2 16 ⎛ ⎝ n 4 ⎞ ⎠ 2   − 1 80 + 1 5(n−3) ⎞ ⎟ ⎠ .

Then, consider the smallest circle containing two points of S chosen uniformly at random, and let Y be the random variable that counts the number of points of S inside this circle. We show an upper bound on the expectation E_S(Y) ≤ [(n−2)/3], and there are point sets S attaining this bound.

Abstract: For every k > 3, we give a construction of planar point sets with many collinear k-tuples and no collinear (k+1)-tuples.

Abstract: Many properties of finite point sets only depend on the relative position of the points, e.g., on the order type of the set. However, many fundamental algorithms in computational geometry rely on coordinate representations. This includes the straightforward algorithms for finding a halving line for a given planar point set, as well as finding a point on the convex hull, both in linear time. In his monograph Axioms and Hulls, Knuth asks whether these problems can be solved in linear time in a more abstract setting, given only the orientation of each point triple, i.e., the set's chirotope, as source of information. We answer this question in the affirmative for sets realizable in the Euclidean plane. More precisely, we can find a halving line through any given point, as well as the vertices of the convex hull edges that are intersected by the supporting line of any two given points of the set in linear time.

Abstract: In the 1.5D terrain guarding problem we are given a polygonal region in the plane determined by an x-monotone polygonal chain, and the objective is to find the minimum number of guards for the given input terrain.The only previous theoretical results about this problem are about approximation. We turn to fixed-parameter tractability. We study "depth of terrain onion peeling" as parameter and show that 1.5D terrain guarding problem is fixed-parameter tractable with respect to this parameter

Abstract: We show that, for any integer k > 2, the Sparse-Yao graph (also known as Yao-Yao graph) YY_4k constructed under the L_∞ norm, is a spanner.

Abstract: The embedding of a digital watermark in vector data results in a perturbation of the vertices which needs to be constrained in order to maintain geometric properties of the data. In this paper we investigate the problem of computing so-called perturbation regions in which the vertices of a planar straight-line graph may be dislocated while still preserving the topology of the input. We propose two different algorithms to solve this problem and discuss how they can form the geometric part of a watermarking framework.

Abstract: In this paper we extend the concept of matched drawability to aligned matched drawability of triple and quadruples of graphs and develop algorithms for constructing such drawings for quadruples and triples of wheels. We also introduce a new class of graphs called double-rim wheel and develop algorithms for constructing aligned matched drawing for triples consisting of two wheels and a tree or a double-rim wheel.

Abstract: We provide a precise description of the class of graphs that admit an one-bend drawing, i.e., an orthogonal drawing with at most one bend per edge. The main tools for the proof are Eulerian orientations and discrete harmonic functions.

Abstract: A previous algorithm was computing the Delaunay triangulation of the flat torus, by using a 9-sheeted covering space. We propose a modification of the algorithm using only a 8-sheeted covering space, which allows to work with 8 periodic copies of the input points instead of 9. The main interest of our contribution is not only this result, but most of all the method itself: this new construction of covering spaces generalizes to Delaunay triangulations of surfaces of higher genus.

Abstract: We present a linear time algorithm for computing the queue-numbers of maximal outerplanar graphs.

Abstract: We study the problem of reconstructing convex sets using only a finite number of measurements of normal vectors. More precisely, we suppose that the normal vectors we are measuring come from independent random points uniformly distributed along the boundary of our convex sets. Given a target Hausdorff error epsilon, we are interested in upper bounding on the number of probes that one has to perform in order to obtain an epsilon-approximation of this convex with high probability. Our results makes use of the stability theory related to Minkowski's theorem.

Abstract: The Delaunay triangulation of n points in the plane can be constructed in o(n logn) time when the coordinates of the points are integers from a restricted range. However, algorithms that are known to achieve such running times had not been implemented so far. We explore ways to obtain a practical algorithm for Delaunay triangulations in the plane that runs in linear time for small integers. For this, we first implement and evaluate variants of an algorithm, BrioDC, that is known to achieve this bound. We find that our implementations of these algorithms are by a reasonable constant factor slower than the fastest known algorithms. Secondly, we implement and evaluate variants of an algorithm, BRIO, that runs fast in experiments. Our variants aim to avoid bad worst-case behavior, but contrary to our expectation, they do not improve the running time.

Abstract: We present an efficient output-sensitive algorithm and its exact implementation to solve the following problem: Given a set S of n line segments in three-dimensional space, find all the lines that simultaneously intersect quadruples of line segments in S. We refer to this problem as `the lines-through-segments problem', or LTS for short. The algorithm properly handles all degenerate cases. Since we do not assume general position, we compute all lines that intersect at least four segments in S. The algorithm runs in O((n³ + I)logn) time, and requires O(n + I) working space, where I is the output size; I is bounded by O(n⁴). We use CGAL arrangements and in particular its support for two-dimensional arrangements in the plane and on the sphere to efficiently compute the intersecting lines in an exact manner. We also report on the performance of our algorithm and its implementation compare it to others. The source code of the LTS program as well as the input examples for the experiments can be obtained from http://acg.cs.tau.ac.il/projects/lts.

Abstract: The Fréchet distance is a metric to compare two curves, which is based on monotonous matchings between these curves. We call a matching that results in the Fréchet distance a Fréchet matching. There are often many different Fréchet matchings and not all of these capture the similarity between the curves well. We propose to restrict the set of Fréchet matchings to "natural" matchings and to this end introduce locally correct Fréchet matchings. We prove that at least one such a matching exists for two polygonal curves and give an algorithm to compute it.

Abstract: The farthest line-segment Voronoi diagram shows properties surprisingly different than the farthest point Voronoi diagram: Voronoi regions may be disconnected and they are not characterized by convex-hull properties. In this paper we introduce the farthest line-segment hull, a cyclic structure that relates to the farthest line-segment Voronoi diagram similarly to the way an ordinary convex hull relates to the farthest-point Voronoi diagram and provide O(n log n)-time algorithms for its construction. Using the farthest line-segment hull, we derive a tighter bound on the (linear) size of the farthest line-segment Voronoi diagram. We also illustrate properties of the L_∞ farthest line-segment Voronoi diagram, which finds applications in VLSI Design Automation.

Abstract: We present an efficient method for collision detection in the black-box KDS model for a set S of n objects in the plane. In this model we receive the object locations at regular time steps and we know a bound d_max on the maximum displacement of any object within one time step. Our method maintains, in O((λ+ k)n) time per time step, a compressed quadtree on the bounding-box vertices of the objects; here λ denotes the density of S and k denotes the maximum number of objects that can intersect any disk of radius d_max . Collisions can then be detected by testing O((λ+k)² n) pairs of objects for intersection.

Abstract: We study online strategies for autonomous mobile robots with vision to explore unknown polygons with at most one hole. We prove lower bounds on the competitive ratio of such strategies both for the orthogonal and the general case. Furthermore we describe a competitive strategy for the case that the robot can distinguish between the edges of the outer boundary and the hole.

Abstract: We revisit the randomized internal-memory algorithm of Abam and Har-Peled for constructing a semi-separated pair decomposition (SSPD) of N points in R^d in the context of the cache-oblivious model of computation. Their algorithm spends O(N ϵ^−d log₂N) time (assuming that the floor function can be evaluated in constant time, O(N ϵ^−d log²₂ N) time otherwise) in expectation and produces a linear-sized SSPD in which each point participates in only a logarithmic number of pairs with high probability. Using a modified analysis of their algorithm and several cache-oblivious techniques for tree construction, labeling, and traversal, we obtain a cache-oblivious algorithm that spends an expected number of O(sort(Nϵ^−d) log₂ N) memory transfers.

Abstract: We define the triangulation axis of a simple polygon P as an anisotropic medial axis of P whose 'unit disks' are line segments or triangles. The underlying triangulation that specifies the anisotropy can be varied, to adapt the axis so as to reflect predominant geometrical and topological features of P. Triangulation axes are piecewise linear skeletons, and typically have much fewer edges and branchings than the Euclidean medial axis or the straight skeleton of P (between n−2 and 2n−6 edges, compared to 2n−3). Still, they retain important properties, as for example the reconstructability of P from its skeleton. Triangulation axes can be easily computed from their defining triangulations in O(n) time. We investigate the effect of using several optimal triangulations for P. In particular, careful edge flipping in the constrained Delaunay triangulation leads, in O(n logn) overall time, to an axis competitive to high quality axes requiring O(n³) time for optimization via dynamic programming.

Abstract: Let S be a finite set of points included in a bounded polygonal domain D of the plane. The order-k nearest influence region of a point in S is the set of points of D having the given point between their k-nearest neighbors in S. Let P be a weighted partition of the domain D into polygonal regions, each region with an associated non-negative weight. We want to solve the problem of finding a new point s of D such that maximizes the weighted area of its order-k nearest influence region with respect to S ∪{s}, that is the sum of the weighted areas of the regions obtained intersecting the order-k nearest influence region with the regions of P. We present a GPU parallel approach, designed under CUDA architecture, for approximately solving the problem and also provide experimental results obtained with its implementation that show the efficiency and scalability of the approach.

Abstract: We study several one-to-one point set matching problems which are motivated by layout problems for grid maps. We are given two sets A and B of n points in the plane, and we wish to compute an optimal one-to-one matching between A and B. We consider two optimisation criteria: minimising the sum of the L₁-distances between matched points, and maximising the number of pairs of points in A for which the matching preserves the directional relation. We show how to minimise the total L₁-distance under translation or scaling in O(n⁶ log³ n) time, and under both translation and scaling in O(n¹⁰ log³ n) time. We further give a 4-approximation for preserving directional relations by computing a minimum L₁-distance matching in O(n² log³ n) time.

Abstract: Let S be a set of n point sites in R^d. A bounded set C ⊂ R^d is to be distributed among the sites p ∈ S such that (i), each p receives a subset C_p of prescribed volume and (ii), the average distance of all points z of C from their respective sites p is minimized. In our model, volume is quantified by a measure μ, and the distance between a site p and a point z is given by a function d_p(z). Under quite liberal technical assumptions on C and on the functions d_p(·) we show that a solution of minimum total cost can be obtained by intersecting with C the Voronoi diagram of the sites in S, based on the functions d_p(·) equipped with suitable additive weights. Moreover, this optimum partition is unique, up to subsets of C of measure zero. Unlike the the deep analytic methods of classical transportation theory, our proof is based on direct geometric arguments.

Abstract: We consider the combinatorial question of how many convex polygons can be made by unions of triangles taken from a fixed triangulation. For general triangulations there can be exponentially many, but if the triangulation is fat (every triangle has its angles lower bounded by a fixed constant δ > 0), then there can only be polynomially many. We provide both lower and upper bounds in both settings.

Abstract: We investigate the higher-order Voronoi diagrams in the L₁ metric in the presence of a transportation network, which is commonly referred to as city metric. For the structural complexity of kth-order city Voronoi diagrams we show a lower bound of Ω(n+kc) and an upper bound of O(k(n−k)+kc), where c is the complexity of the transportation network. This is quite different from the bound O(k(n−k)) in the Euclidean metric, especially for the case when k=n−1. Furthermore, we develop an O(k²(n+c) logn)-time algorithm for the kth-order city Voronoi diagram and an O(nc log²(n+c) logn)-time algorithm for the farthest-site city Voronoi diagram.

Abstract: It is a well-known fact that the restricted Delaunay and witness complexes may differ when the landmark and witness sets are located on submanifolds of R^d of dimension 3 or more. Currently, the only known way of overcoming this issue consists of building some crude superset of the witness complex, and applying a greedy sliver exudation technique on this superset. Unfortunately, the construction time of the superset depends exponentially on the ambient dimension, which makes the witness complex based approach to manifold reconstruction impractical. This work provides an analysis of the reasons why the restricted Delaunay and witness complexes fail to include each other. From this a new set of conditions naturally arises under which the two complexes are equal.

Abstract: Two plane graphs with the same vertex set are compatible if their union is again a plane graph. We consider bichromatic plane straight-line graphs with vertex set S consisting of the same number of red and blue points, and (perfect) matchings which are compatible to them. For several different classes C of graphs, we present lower and upper bounds such that any given graph G(S) ∈ C admits a compatible (perfect) matching with this many disjoint edges.

Abstract: We extend the notion of canonical orderings (and underlying Schnyder woods) to cylindric triangulations. This allows us to extend the incremental straight-line drawing algorithm of de Fraysseix et al. to this setting. Our algorithm yields in linear time a crossing-free straight-line drawing of a cylindric triangulation T with n vertices on a regular grid Z/w Z ×[0,h], with w ≤ 2n and h ≤ n(n−3)/2. As a by-product, we can also obtain in linear time a crossing-free straight-line drawing of a toroidal triangulation with n vertices on a periodic regular grid Z/w Z ×Z/h Z, with w ≤ 2n and h ≤ n(n+3)/2.

Abstract: We present a new algorithm for lune-based β-skeletons for sets of n points in the plane, for β ∈ (2,∞], the only case when optimal algorithms are not known. The running time of the algorithm is O(n^3/2 log^1/2 n), which is the best known and is an improvement of Rao and Mukhopadhyay result. The method is based on point location in monotonic subdivisions of arrangements of curve segments.

Abstract: In this paper, we complete the study of the length of a longest Delaunay edge for points randomly distributed in multidimensional Euclidean spaces carried out in [1]. The Delaunay graph is defined over a set of n points distributed uniformly at random in a d-dimensional body of unit volume, assuming that the probability that those points are not in general position is negligible. The motivation to study this problem comes from its application in energy-efficient geometric routing and flooding in wireless sensor networks. Given that the length of the longest Delaunay edge is strongly influenced by the boundary of the enclosing region, in [1] we study the problem for the surface of a d-sphere and the volume of a d-ball. The results presented in that work include upper and lower bounds for d-dimensional bodies with and without boundaries, that hold for a parametric error probability. Lower bounds for a d-ball were proved only for d ≤ 3 leaving open the question for higher dimensions. We answer this question in the present work presenting a lower bound that holds in general for any d > 1, and we also compute the particular cases d=2 and d=3 to obtain the precise bound on the euclidean distance. These lower bounds are proved showing that a configuration that yields a Delaunay edge of a certain length occurs with probability at least a parameter epsilon. These lower bounds are computed up to constants and are asymptotically tight for e^−cn ≤ ϵ ≤ n^−c, for any constant c > 0, and constant d. To the best of our knowledge, the present work and [1] are the first comprehensive study of this problem. [1] E. Arkin, A. Fernandez Anta, J.S.B. Mitchell, and M.A. Mosteiro. Probabilistic Bounds on the Length of a Longest Edge in Delaunay Graphs of Random Points in d-Dimensions. CCCG 2011.

Abstract: We show that every convex polyhedron may be unfolded to one planarpiece, and then refolded to a different convex polyhedron.If the unfolding is restricted to cut only edges of the polyhedron,then the dodecahedron is ëdge-unfold rigid" in the sense that allof its 43,380 edge unfoldings may only fold back to the dodecahedron.We begin the exploration of which polyhedra are edge-unfold rigid,identifying one infinite rigid class, perturbed dodecahedra,and one infinite nonrigid class: tetrahedra.A 9-page version of this paper, with more figures and all proofsincluded, is available at http://cs.smith.edu/~orourke/Unf/RefoldRigidEuroCGFull.pdf.

Abstract: Let S=R∪B be a set of n points in general position in the plane. The elements of R and B will be called, respectively, the red and blue elements of S. A k-hole of S is a simple polygon with k vertices, all in S, and containing no element of S in its interior. A 4-hole of S is balanced is if it has two blue and two red vertices. In this paper, we characterize the set of bicolored points S=R ∪B that have balanced convex 4-holes. We also show that if the 4-holes of S are allowed to be non-convex, then if S=R ∪B, and |R|=|B|, then S always has a quadratic number of balanced 4-holes.

Abstract: We consider the problem of computing an order type invariant labeling for a given set of n points. In 2D, such a labeling can be constructed in O(hn²) time, where h is the size of the smallest convex layer. In 3D the time complexity is O(n³ logn) if the point set is in general position. This is useful to test if two point sets have the same order type within the same time bounds. It can also be used as preprocessing for any order type invariant algorithm, such as triangulation/tetrahedralization, or polygonization.

Abstract: In this paper we deal with the page number problem for partially ordered sets (posets) restricted to the family of N-free posets. We calculate this number exactly for tree-structured N-free posets and for tree-structured N-free planar posets. Some other results are also mentioned.

Abstract: Let S=p₁,...,p_n be a set of n points in the plane in general position. A quadrant Q of the plane is the intersection of two closed half-planes whose supporting lines are parallel to the x and y-axes. We say that a quadrant is S-free if it does not contain any point of S in int(Q), where int(Q) denotes the interior of Q. The rectilinear convex hull RH(S) of S is defined as the plane minus the union of S-free quadrants. The rectilinear convex layers of S are defined as follows:

1. The first rectilinear convex layer of S, denoted L₁, is RH(S). Let S₁ denote the set of elements of S that belong to RH(S).
2. The i-th rectilinear convex layer L_i of S is the rectilinear convex hull RH(S_i), where S_i = S \{S₁ ∪... ∪S_i-1 }, where S_j is the set of elements of S in L_j . We stop when S \{S₁ ∪... ∪S_i } is empty; the first i for which S \{S₁ ∪... ∪S_i } is empty is the number of rectilinear convex layers of S.

In this paper, we give an O(n logn) time algorithm to calculate the rectilinear convex layers of S. We also give an O(n² log n) time algorithm to calculate the rotation of S that minimizes the number of rectilinear convex layers of S.

Abstract: The problem of searching a polygonal region for an unpredictably moving intruder by a set of stationary guards, each carrying an orientable laser, is known as the Searchlight Scheduling Problem. Determining the complexity of deciding if the entire area can be searched is a long-standing open problem. Recently, the author introduced the Partial Searchlight Scheduling Problem, in which only a given subregion of the environment has to be searched, and proved that its 3-dimensional decisional version is PSPACE-hard, even when restricted to orthogonal polyhedra. Here we extend and refine this result, by proving that 2-dimensional Partial Searchlight Scheduling is strongly PSPACE-complete, both in general and restricted to orthogonal polygons in which the region to be searched is a rectangle.

Abstract: Let C be a set of n fat objects of arbitrary sizes in R^d whose packing and piercing numbers are denoted by Pack(C), and Pierce(C), respectively. We derive the first sub-exponential time algorithms for computing the exact value of Pack(C) and Pierce(C), respectively, in n^{O( Pack(C)[(d−1)/d])} and n^{O( Pierce(C)[(d−1)/d])} time and O(nlogn) storage. Our methods build upon the separation theorems derived by Chan, and Smith and Wormald. Specifically, we also derive a 1/3−2/3 measure separation theorem with relatively small constants for fat objects, as our mail tool, that is interesting in its own way. The results readily give rise to polynomial time approximation schemes (PTAS) that run in n^{O([1/(ϵ)]d−1)} time and O(nlogn) storage

Abstract: The goal of this paper is to give an overview of the results and open questions in the area of long alternating paths and separated matchings. We also include a new proof of the construction class of Hajnal and Mészáros showing there are at most [4/3]n+O(√n) points in any noncrossing alternating path on a specific convex 2n-element equally two-colored planar point set. This is currently the best upper bound and it is conjectured to be asymptotically tight. The survey is written based on my Ph.D. thesis.

Abstract: The theory of optimal size meshes gives a method for analyzing the output size of a Delaunay refinement mesh in terms of the integral of a sizing function over the space. The input points define a maximal such sizing function called the feature size. Integrating the feature size function over input domain is not easy, and historically, was not deemed necessary. Matching upper and lower bounds in terms of this integral seemed sufficient. However, a new analysis of the feature size integral led to linear-size Delaunay meshes, the Scaffold Theorem relating surface and volume meshes, and a time-optimal output- sensitive point meshing algorithm. The key idea is to consider the pacing of an ordered point set, a measure of the rate of change in the feature size as points are added one at a time. In previous work, Miller et al. showed that if an ordered point set has pacing φ, then the number of vertices in an optimal mesh will be O(φd n), where d is the input dimension. We give a new analysis of this integral showing that the output size is only O(n logφ). The new analysis tightens all of the previous results mentioned above and provides matching lower bounds.

Abstract: We prove that every outerplanar graph with maximum degree ∆ ≥ 4 has a straight-line outerplanar drawing with at most ∆−1 distinct edge slopes. This bound is tight: for every ∆ ≥ 4 there is an outerplanar graph of maximum degree ∆ which requires at least ∆−1 distinct edge slopes for its outerplanar straight-line drawing.

Abstract: Let G be a graph cellularly embedded in a surface S orientable or not, and with at least a boundary. Given two closed walks c and d in G, we describe linear time algorithms to decide if c and d are homotopic in S, either freely or with fixed basepoint. After O(|G|) time preprocessing independent of c and d, our algorithms answer the homotopy test in O(|c| + |d|) time, where |G|, |c| and |d| are the respective numbers of edges of G, c and d.

Abstract: A uniform approach is proposed to solving three fundamental problems related to zonotopes given by generator description - the facet enumeration, the vertex enumeration and the volume computation. The common algorithmic frame is designed, which allows to solve all the three problems simultaneously. The proposed algorithm is compact for the facet enumeration and volume computation.

Abstract: We address the problem of counting empty pseudo-triangles defined by a set of points in the plane. First, we assume that the three convex vertices are fixed, and provide algorithms, which solve the respective problem in O(n²) time using O(n) space, for the cases when the pseudo-triangles can be arbitrary or must be star-shaped. The relaxation of our assumption increases the time complexity by factor n³ in either case.