Define an arrangement of double pseudolines as a finite family of at least two separating simple closed curves embedded in a projective plane, with the property that any two meet transversally in exactly four points and induce a cell structure on the projective plane. We show that any arrangement of double pseudolines is isomorphic to the dual family of a finite family of pairwise disjoint convex bodies of a projective plane endowed with a topological point-line incidence geometry and we provide a simple axiomatic characterization of the class of isomorphism classes of indexed arrangements of oriented double pseudolines.

We present an algorithm to enumerate the pointed pseudotriangulations of a given point set, based on the greedy flip algorithm of Pocchiola and Vegter [Discrete Comput. Geom. 16 (1996), pp. 419–453]. Our two independent implementations agree and allow us to experimentally verify or disprove conjectures on the numbers of pointed pseudotriangulations and triangulations of a given point set. (For example, we establish that the number of triangulations is bounded by the number of pointed pseudotriangulations for all sets of up to 10 points.)

We present a new and simpler method to implement in constant amortized time the flip operation of the so-called “Greedy Flip Algorithm”, an optimal algorithm to compute the visibility complex of a collection of pairwise disjoint bounded convex sets of constant complexity. The method relies on a “sum of squares” like theorem for visibility complexes stated and proved in this paper. (The sum of squares theorem for an arrangement of lines states that the average value of the square of the number of vertices of a face of the arrangement is a $O(1)$.)

A closed orientable surface of genus $g$ can be obtained by appropriat e identification of pairs of edges of a $4g$-gon (the polygonal schema). The identified edges form $2g$ loops on the surface, that are disjoint except for their common end-point. These loops are generators of both the fundamental group and the homology group of the surface. The inverse problem is concerned with finding a set of $2g$ loops on a triangulated surface, such that cutting the surface along these loops yields a (canonical) polygonal schema. We present two optimal algorithms for this inverse problem. Both algorithms have been implemented using the CGAL polyhedron data structure.

We show that the k free bitangents of a collection of n pairwise disjoint convex plane sets can be computed in time O(k+n log n) and O(n) working space. The algorithm uses only one advanced data structure, namely a splittable queue. We introduce (weakly) greedy pseudo--triangulations, whose combinatorial properties are crucial for our method. 1 Introduction Consider a collection O of pairwise disjoint convex objects in the plane. We are interested in problems in which these objects arise as obstacles, either in connection with visibility problems where they can block the view from an other geometric object, or in motion planning, where these objects may prevent a moving object from moving along a straight line path. The visibility graph is a central object in such contexts. For polygonal obstacles the vertices of these polygons are the nodes of the visibility graph, and two nodes are connected by an arc if the corresponding vertices can see each other. [9] describes the first non-triv...

We introduce the visibility complex of a collection O of n pairwise disjoint convex objects in the plane. This 2 dimensional cell complex may be considered as a generalization of the tangent visibility graph of 0. Its space complexity k is proportional to the size of the tangent visibility graph. We give an O(nlog n+k) algorithm for its construction. Furthermore we show how the visibility complex can be used to compute the view from a point or a convex object with respect to O in O(m log n) time, where m is the size of the view. The view from a point is a generalization of the visibility polygon of that point with respect to O.

We study enumeration and visibility problems in the d-dimensional integer lattice Ldn of d-tuples of integers ≤ n. In the first part of the paper we give several useful enumeration principles and use them to study the asymptotic behavior of the number of straight lines traversing a certain fixed number of lattice vertices of Ldn, the line incidence problem and the edge visibility region. In the second part of the paper we consider an art gallery problem for point obstacles. More specifically we study the camera placement problem for the infinite lattice Ld. A lattice point is visible from a camera C (positioned at a vertex of Ld) if the line segment joining A and C crosses no other lattice vertex. For any given number s ≤ 3d of cameras we determine the position they must occupy in the lattice Ld in order to maximize their visibility.