skip to main content


Search for: All records

Creators/Authors contains: "Dani, Varsha"

Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher. Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?

Some links on this page may take you to non-federal websites. Their policies may differ from this site.

  1. Rajsbaum, Sergio ; Balliu, Alkida ; Daymude, Joshua J. ; Olivetti, Dennis (Ed.)
    We address the problem of designing a distributed algorithm for two robots that sketches the boundary of an unknown shape. Critically, we assume a certain amount of delay in how quickly our robots can react to external feedback. In particular, when a robot moves, it commits to move along path of length at least λ, or turn an amount of radians at least λ for some positive λ ≤ (1/2)^6, that is normalized based on a unit diameter shape. Then, our algorithm outputs a polygon that is an ϵ-sketch, for ϵ = 8λ^(1/2), in the sense that every point on the shape boundary is within distance ϵ of the output polygon. Moreover, our costs are asymptotically optimal in two key criteria for the robots: total distance travelled and total amount of rotation. Additionally, we implement our algorithm, and illustrate its output on some specific shapes. 
    more » « less
    Free, publicly-accessible full text available July 1, 2024
  2. Bojanczyk, M. et (Ed.)
    Embedding graphs in a geographical or latent space, i.e. inferring locations for vertices in Euclidean space or on a smooth manifold or submanifold, is a common task in network analysis, statistical inference, and graph visualization. We consider the classic model of random geometric graphs where n points are scattered uniformly in a square of area n, and two points have an edge between them if and only if their Euclidean distance is less than r. The reconstruction problem then consists of inferring the vertex positions, up to the symmetries of the square, given only the adjacency matrix of the resulting graph. We give an algorithm that, if r = n^α for α > 0, with high probability reconstructs the vertex positions with a maximum error of O(n^β) where β = 1/2-(4/3)α, until α ≥ 3/8 where β = 0 and the error becomes O(√{log n}). This improves over earlier results, which were unable to reconstruct with error less than r. Our method estimates Euclidean distances using a hybrid of graph distances and short-range estimates based on the number of common neighbors. We extend our results to the surface of the sphere in ℝ³ and to hypercubes in any constant dimension. 
    more » « less
  3. null (Ed.)
  4. null (Ed.)