Search results for "Computer Science::Computational Geometry"
showing 10 items of 70 documents
Generation of Valid Labeled Binary Trees
2003
International audience; Generating binary trees is a well-known problem. In this paper, we add some constraints to leaves of these trees. Such trees are used in the morphing of polygons, where a polygon P is represented by a binary tree T and each angle of P is a weight on a leaf of T. In the following, we give two algorithms to generate all binary trees, without repetitions, having the same weight distribution to their leaves and representing all parallel polygons to P.
Combinatorial aspects of L-convex polyominoes
2007
We consider the class of L-convex polyominoes, i.e. those polyominoes in which any two cells can be connected with an ''L'' shaped path in one of its four cyclic orientations. The paper proves bijectively that the number f"n of L-convex polyominoes with perimeter 2(n+2) satisfies the linear recurrence relation f"n"+"2=4f"n"+"1-2f"n, by first establishing a recurrence of the same form for the cardinality of the ''2-compositions'' of a natural number n, a simple generalization of the ordinary compositions of n. Then, such 2-compositions are studied and bijectively related to certain words of a regular language over four letters which is in turn bijectively related to L-convex polyominoes. In …
Finite linear spaces in which any n-gon is euclidean
1986
Abstract An n-gon of a linear space is a set S of n points no three of which are collinear. By a diagonal point of S we mean a point p off S with the property that at least two lines through p intersect S in two points. The number of diagonal points is called the type of S. For example, a 4-gon has at most three diagonal points. We call an n-gon euclidean if (roughly speaking) it contains the maximal possible number of 4-gons of type 3. In this paper, we characterize all finite linear spaces in which, for a fixed number n ⩾ 5, any n-gon is euclidean. It turns out that these structures are essentially projective spaces or punctured projective spaces.
Ordering and Convex Polyominoes
2005
We introduce a partial order on pictures (matrices), denoted by ≼ that extends to two dimensions the subword ordering on words. We investigate properties of special families of discrete sets (corresponding to {0,1}-matrices) with respect to this partial order. In particular we consider the families of polyominoes and convex polyominoes and the family, recently introduced by the authors, of L-convex polyominoes. In the first part of the paper we study the closure properties of such families with respect to the order. In particular we obtain a new characterization of L-convex polyominoes: a discrete set P is a L-convex polyomino if and only if all the elements Q≼P are polyominoes. In the seco…
Reconstruction of L-convex Polyominoes.
2003
Abstract We introduce the family of L-convex polyominoes, a subset of convex polyominoes whose elements satisfy a special convexity property. We develop an algorithm that reconstructs an L-convex polyomino from the set of its maximal L-polyominoes.
"Table 5" of "Properties of hadronic Z decays and test of QCD generators"
1992
Planarity distribution.
"Table 6" of "Properties of hadronic Z decays and test of QCD generators"
1992
Planarity distribution.
On the exhaustive generation of k-convex polyominoes
2017
The degree of convexity of a convex polyomino P is the smallest integer k such that any two cells of P can be joined by a monotone path inside P with at most k changes of direction. In this paper we present a simple algorithm for computing the degree of convexity of a convex polyomino and we show how it can be used to design an algorithm that generates, given an integer k, all k-convex polyominoes of area n in constant amortized time, using space O(n). Furthermore, by applying few changes, we are able to generate all convex polyominoes whose degree of convexity is exactly k.
Bézier solutions of the wave equation
2004
We study polynomial solutions in the Bezier form of the wave equation in dimensions one and two. We explicitly determine which control points of the B´ezier solution at two different times fix the solution.
An Efficient Algorithm for Helly Property Recognition in a Linear Hypergraph
2001
International audience; In this article we characterize bipartite graphs whose associated neighborhood hypergraphs have the Helly property. We examine incidence graphs both hypergraphs and linear hypergraphs and we give a polynomial algorithm to recognize if a linear hypergraph has the Helly property.