Search

A variation on the classical polygon illumination problem was introduced in [Aichholzer et al. EuroCG'09]. In this variant light sources are replaced by wireless devices called -modems, which can penetrate a fixed number , of 'walls'. A point in the interior of a polygon is 'illuminated' by a -modem if the line segment joining them intersects at most edges of the polygon. It is easy to construct polygons of vertices where the number of -modems required to illuminate all interior points is . However, no non-trivial upper bound is known. In this paper we prove that the number of kmodems required to illuminate any polygon of vertices is . For the cases of illuminating an orthogonal polygon or a set of disjoint orthogonal segments, we give a tighter bound of . Moreover, we present an time algorithm to achieve this bound. [ABSTRACT FROM AUTHOR]

It is an open problem to find a good characterization for independence or, more generally, the rank function in the d-dimensional rigidity matroid of a graph when d ≥ 3. In this paper we give a brief survey of existing lower and upper bounds on the rank of the 3-dimensional rigidity matroid of a graph and introduce a new upper bound, which may lead to the desired good characterization. [ABSTRACT FROM AUTHOR]

Our approach exploits a general-purpose decomposition algorithm, called GPDOF, and a dictionary of very efficient solving procedures, called r-methods, based on theorems of geometry. GPDOF decomposes an equation system into a sequence of small subsystems solved by r-methods, and produces a set of input parameters.1. Recursive assembly methods (decomposition-recombination), maximum matching based algorithms, and other famous propagation schema are not well-suited or cannot be easily extended to tackle geometric constraint systems that are under-constrained. In this paper, we show experimentally that, provided that redundant constraints have been removed from the system, GPDOF can quickly decompose large under-constrained systems of geometrical constraints. We have validated our approach by reconstructing, from images, 3D models of buildings using interactively introduced geometrical constraints. Models satisfying the set of linear, bilinear and quadratic geometric constraints are optimized to fit the image information. Our models contain several hundreds of equations. The constraint system is decomposed in a few seconds, and can then be solved in hundredths of seconds. [ABSTRACT FROM AUTHOR]

In this paper, we consider a map labeling problem where the points to be labeled are restricted on a line. It is known that the 1d-4P and the 1d-4S unit-square label placement problem and the Slope-4P unit-square label placement problem can both be solved in linear time and the Slope-4S unit-square label placement problem can be solved in quadratic time in Ref. [8]. We extend the result to the following label placement problem: Slope-4P fixed-height (width) label or elastic label placement problem and present a linear time algorithm for it provided that the input points are given sorted. We further show that if the points are not sorted, the label placement problems have a lower bound of Ω(n log n), where n is the input size, under the algebraic computation tree model. Optimization versions of these point labeling problems are also considered. [ABSTRACT FROM AUTHOR]

Classical topology-based operations such as extrusion (or more generally Minkowski sums) are defined by a cartesian product of combinatorial structures describing the topology of geometric space subdivisions. In this paper, we define the cartesian product operation for four different structures: semi-simplicial sets, generalized maps, oriented maps and chains of maps. We follow a homogeneous framework allowing to define the cartesian product for any simplicial and cellular structures derived from simplicial sets and combinatorial maps. This results from the relationships already established between these structures and those used in computational geometry and geometric modeling. For esch structure we have studied, we additionally provide a time-optimal computation algorithm. [ABSTRACT FROM AUTHOR]

Deciding 3-colorability for general plane graphs is known to be an NP-complete problem. However, for certain families of graphs, like triangulations, polynomial time algorithms exist. We consider the family of pseudo-triangulations, which are a generalization of triangulations, and prove NP-completeness for this class. This result also holds if we bound their face degree to four, or exclusively consider pointed pseudo-triangulations with maximum face degree five. In contrast to these completeness results, we show that pointed pseudo-triangulations with maximum face degree four are always 3-colorable. An according 3-coloring can be found in linear time. Some complexity results relating to the rank of pseudo-triangulations are also given. [ABSTRACT FROM AUTHOR]

Motivated by a crane assignment problem, we consider a Euclidean bipartite matching problem with edge-crossing constraints. Specifically, given red points and blue points in the plane, we want to construct a perfect matching between red and blue points that minimizes the length of the longest edge, while imposing a constraint that no two edges may cross each other. We show that the problem cannot be approximately solved within a factor less than 1:277 in polynomial time unless . We give simple dynamic programming algorithms that solve our problem in two special cases, namely (1) the case where the red and blue points form the vertices of a convex polygon and (2) the case where the red points are collinear and the blue points lie to one side of the line through the red points. [ABSTRACT FROM AUTHOR]

We consider the problem of computing the discrete Fréchet distance between two polygonal curves when their vertices are imprecise. An imprecise point is given by a region and this point could lie anywhere within this region. By modelling imprecise points as balls in dimension d, we present an algorithm for this problem that returns in time 2O(d2)m2n2log2(mn) the minimum Fréchet distance between two imprecise polygonal curves with n and m vertices, respectively. We give an improved algorithm for the planar case with running time O(mn log3(mn) + (m2+n2)log (mn)). In the d-dimensional orthogonal case, where points are modelled as axis-parallel boxes, and we use the L∞ distance, we give an O(dmn (dmn))-time algorithm. We also give efficient O(dmn)-time algorithms to approximate the maximum Fréchet distance, as well as the minimum and maximum Fréchet distance under translation. These algorithms achieve constant factor approximation ratios in "realistic" settings (such as when the radii of the balls modelling the imprecise points are roughly of the same size). [ABSTRACT FROM AUTHOR]

This article examines the computation of the Delaunay graph and its dual Voronoi diagram of a set of ellipses in the Euclidean plane. We propose the first complete methods, under the exact computation paradigm, for the predicates of an incremental algorithm: κ1 decides which one of two given ellipses is closest to a given exterior point; κ2 decides the position of a query ellipse relative to an external bitangent line of two given ellipses; κ3 decides the position of a query ellipse relative to a Voronoi circle of three given ellipses; κ4 determines the type of conflict between a Voronoi edge, defined by four given ellipses, and a query ellipse. The article is restricted to non-intersecting ellipses, but the extension to arbitrary ones is possible. The ellipses are input in parametric representation, i.e., constructively in terms of their axes, center and rotation. For κ1 and κ2 we derive algebraic conditions optimal in terms of the degree of the algebraic numbers involved, and provide efficient implementations in C++. For κ3 we compute a tight bound on the number of complex tritangent circles and design an exact symbolic-numeric algorithm, which is implemented in MAPLE. This essentially answers κ4 as well. We conclude with further work on lifting the condition of non-intersecting ellipses. [ABSTRACT FROM AUTHOR]