Search

Filling operations are procedures which are used in Discrete Tomography for the reconstruction of lattice sets having some convexity constraints. Many algorithms have been published giving fast implementations of these operations, and the best running time [S. Brunetti, A. Daurat, A. Kuba, Fast filling operations used in the reconstruction of convex lattice sets, in: Proc. of DGCI 2006, in: Lecture Notes in Comp. Sci., vol. 4245, 2006, pp. 98–109] is O(N2logN) time, where N is the size of projections. In this paper we improve this result by providing an implementation of the filling operations in O(N2). As a consequence, we reduce the time-complexity of the reconstruction algorithms for many classes of lattice sets having some convexity properties. In particular, the reconstruction of convex lattice sets satisfying the conditions of Gardner–Gritzmann [R.J. Gardner, P. Gritzmann, Discrete tomography: Determination of finite sets by X-rays, Trans. Amer. Math. Soc. 349 (1997) 2271–2295] can be performed in O(N4)-time.

This paper presents an algorithm for identifying a maximal empty-staircase-polygon (MESP) of largest area, among a set of n points on a rectangular floor. A staircase polygon is an isothetic polygon bounded by two monotonically rising (falling) staircases. A monotonically rising staircase is a sequence of alternatingly horizontal and vertical line segments from the bottom-left corner of the floor to its top-right corner such that for every pair of points α = (xα, yα) and β = (xβ, yβ) on the staircase, xα ≤ xβ implies yα ≤ yβ. A monotonically falling staircase can similarly be defined from the bottom-right corner of the floor to its top-left corner. An empty staircase polygon is a MESP if it is not contained in another larger empty staircase polygon. The problem of recognizing the largest MESP is formulated using permutation graph, and a simple O(n3) time algorithm is proposed. Next, based on certain novel geometric properties of the problem, an improved algorithm is developed that identifies the largest MESP in O(n2) time and space. The algorithm can be easily tailored for identifying the widest MESP in a similar environment. The general problem of locating the largest area/width MESP among a set of isothetic polygonal obstacles, can be solved easily. These geometric optimization problems have several applications to VLSI layout design, robot motion planning, to name a few.

Coalitional Resource Games (crgs) are a form of Non-Transferable Utility (ntu) game, which provide a natural formal framework for modelling scenarios in which agents must pool scarce resources in order to achieve mutually satisfying sets of goals. Although a number of computational questions surrounding crgs have been studied, there has to date been no attempt to develop solution concepts for crgs, or techniques for constructing solutions. In this paper, we rectify this omission. Following a review of the crg framework and a discussion of related work, we formalise notions of coalition structures and the core for crgs, and investigate the complexity of questions such as determining nonemptiness of the core. We show that, while such questions are in general computationally hard, it is possible to check the stability of a coalition structure in time exponential in the number of goals in the system, but polynomial in the number of agents and resources. As a consequence, checking stability is feasible for systems with small or bounded numbers of goals. We then consider constructive approaches to generating coalition structures. We present a negotiation protocol for crgs, give an associated negotiation strategy, and prove that this strategy forms a subgame perfect equilibrium. We then show that coalition structures produced by the protocol satisfy several desirable properties: Pareto optimality, dummy player, and pseudo-symmetry. © 2009 Elsevier B.V. All rights reserved.

In this paper, we consider the problem of reconstructing polyominoes from information about the thickness in vertical and horizontal directions. We focus on the case where there are multiple disjoint polyominoes (of different colours) that are hv-convex, i.e., any intersection with a horizontal or vertical line is contiguous. We show that reconstruction of such polyominoes is polynomial if the number of colours is constant, but NP-hard for an unbounded number of colours.

A polygon P is called k-vertex guardable if there is a subset G of the vertices of P such that each point in P is seen by at least k vertices in G. For the main results of this paper, it is shown that the following number of vertex guards is sufficient and sometimes necessary to k-vertex guard any simple n-gon P without holes: @?2n/[email protected]? are needed for k=2 if P is any n-gon and @?3n/[email protected]? are needed for k=3 if P is any convexly quadrilateralizable n-gon. The proofs for both of the results yield algorithms with O(n^2) runtimes.

The most efficient known construction of equation automaton is that due to Ziadi and Champarnaud. For a regular expression E, it requires O(|E|2) time and space and is based on going from position automaton to equation automaton using c-continuations. This complexity is due to the sorting step that takes O(|E|2) time used to identify the identical sub-expressions of E. In this paper, we present a more efficient construction of the equation automaton which avoids the sorting step and replaces it by a minimization of an acyclic finite deterministic automaton. We show that this minimization allows the identification of identical sub-expressions as well as the sorting step used in Champarnaud and Ziadi's approach. Using the minimization we get O(|E|+|E|⋅|EE|) time and space complexity where |EE| is the number of states of the equation automaton.