archive-lt.com » LT » T » THERAN.LT

Total: 41

Choose link from "Titles, links and description words view":

Or switch to "Titles and links view".
  • Characterizing sparse graphs by map decompositions
    Ileana Streinu and Louis Theran Journal Journal of Combinatorial Mathematics and Combinatorial Computing 62 2007 Full text arXiv A map is a graph that admits an orientation of its edges so that each vertex has out degree exactly 1 We characterize graphs which admit a decomposition into edge disjoint maps after 1 the addition of any edges 2 the addition of some edges These graphs are identified with classes of

    Original URL path: http://theran.lt/papers/j002-maps.html (2016-04-26)
    Open archived version from archive


  • Graded sparse graphs and matroids
    of Universal Computer Science 13 11 1671 1679 2007 Full text arXiv DOI Sparse graphs and their associated matroids play an important role in rigidity theory where they capture the combinatorics of generically rigid structures We define a new family called graded sparse graphs arising from generically pinned completely immobilized bar and joint frameworks and prove that they also form matroids We address five problems on graded sparse graphs Decision

    Original URL path: http://theran.lt/papers/j001-graded.html (2016-04-26)
    Open archived version from archive

  • Delaunay triangulations with disconnected realization spaces
    realization spaces of Delaunay triangulations and show that they can be arbitrarily complicated and in particular disconnected Our smallest example consists of two configurations of labeled points in whose Delaunay triangulations are combinatorially equivalent but yet there is no continuous transformation that maps one to the other without changing the triangulation In general we prove that the realization space of a Delaunay triangulation in can have connected components Our proof

    Original URL path: http://theran.lt/papers/c012-disconnected.html (2016-04-26)
    Open archived version from archive

  • Detecting dependencies in geometric constraint systems
    Computer Aided Design software Automated approaches for detecting dependencies in a design are critical for developing robust solvers and provid ing informative user feedback and we provide algorithms that recognize two types of dependencies First we give a pebble game algorithm for detecting generic dependencies Then we focus on identifying the special positions of a design in which generically independent constraints become dependent We present combinatorial algorithms for identifying subgraphs

    Original URL path: http://theran.lt/papers/c011-special.html (2016-04-26)
    Open archived version from archive

  • Generic rigidity with forced symmetry and sparse colored graphs
    2014 Full text arXiv DOI We review some recent results in the generic rigidity theory of planar frameworks with forced symmetry giving a uniform treatment to the topic We also give new combinatorial characterizations of minimally rigid periodic frameworks with

    Original URL path: http://theran.lt/papers/c010-colored.html (2016-04-26)
    Open archived version from archive

  • Error-Minimizing Estimates and Universal Entry-Wise Error Bounds for Low-Rank Matrix Completion
    13 2013 Full text arXiv URL We propose a general framework for reconstructing and denoising single entries of incomplete and noisy entries We describe effective algorithms for deciding if and entry can be reconstructed and if so for reconstructing and denoising it and a priori bounds on the error of each entry individually In the noiseless case our algorithm is exact For rank one matrices the new algorithm is fast

    Original URL path: http://theran.lt/papers/c009-rank1.html (2016-04-26)
    Open archived version from archive

  • Rigid components in fixed-lattice and cone frameworks
    Geometry CCCG 11 2011 Full text arXiv URL We study the fundamental algorithmic rigidity problems for generic frameworks periodic with respect to a fixed lattice or a finite order rotation in the plane For fixed lattice frameworks we give an algorithm for deciding generic rigidity and an algorithm for computing rigid components If the order of rotation is part of the input we give an algorithm for deciding rigidity in

    Original URL path: http://theran.lt/papers/c008-symmetriccomps.html (2016-04-26)
    Open archived version from archive

  • Searching in tree-like partial orders
    Algorithms and Data Structures WADS 11 2011 Full text arXiv DOI We give the first data structure for the problem of maintaining a dynamic set of n elements drawn from a partially ordered universe described by a tree We define the Line Leaf Tree a linear sized data structure that supports the operations insert delete test membership and predecessor The performance of our data structure is within an factor of

    Original URL path: http://theran.lt/papers/c007-partial.html (2016-04-26)
    Open archived version from archive