Lattices Without a Big Constant and With Noise
We show how Frieze's analysis of subset sum solving using lattices can be done with out any large constants and without flipping. We apply the variant without the large constant to inputs with noise.
Source author record
Steven J. Gortler
Steven J. Gortler appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.
ResearcherUnclaimed source record
Catalog footprint
What is connected
17works
13topics
4close collaborators
Research graph
See the researcher in context
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
Building this map preview
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
17 published item(s)
preprint2022arXiv
Universal Rigidity of Ladders on the line
In "Universal rigidity on the line, point orde" it is shown, answering a question of Jordán and Nguyen, that universal rigidity of a generic bar-joint framework in R^1 depends on more than the ordering of the vertices. The graph G that was used in that paper is a ladder with three rungs. Here we provide a general answer when that ladder with three rungs in the line is universally rigid and when it is not.
0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv
Determining Generic Point Configurations From Unlabeled Path or Loop Lengths
Let $\mathbf{p}$ be a configuration of $n$ points in $\mathbb{R}^d$ for some $n$ and some $d \ge 2$. Each pair of points defines an edge, which has a Euclidean length in the configuration. A path is an ordered sequence of the points, and a loop is a path that has the same endpoints. A path or loop, as a sequence of edges, also has a Euclidean length. In this paper, we study the question of when $\mathbf{p}$ will be uniquely determined (up to an unknowable Euclidean transform) from a given set of path or loop lengths. In particular, we consider the setting where the lengths are given simply as a set of real numbers, and are not labeled with the combinatorial data describing the paths or loops that gave rise to the lengths. Our main result is a condition on the set of paths or loops that is sufficient to guarantee such a unique determination. We also provide an algorithm, under a real computational model, for performing a reconstruction of $\mathbf{p}$ from such unlabeled lengths. To obtain our results, we introduce a new family of algebraic varieties which we call the unsquared measurement varieties. The family is parameterized by the number of points $n$ and the dimension $d$, and our results follow from a complete characterization of the linear automorphisms of these varieties for all $n$ and $d$. The linear automorphisms for the special case of $n = 4$ and $d = 2$ correspond to the so-called Regge symmetries of the tetrahedron.
0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv
Almost-rigidity of frameworks
We extend the mathematical theory of rigidity of frameworks (graphs embedded in $d$-dimensional space) to consider nonlocal rigidity and flexibility properties. We provide conditions on a framework under which (I) as the framework flexes continuously it must remain inside a small ball, a property we call "almost-rigidity"; (II) any other framework with the same edge lengths must lie outside a much larger ball; (III) if the framework deforms by some given amount, its edge lengths change by a minimum amount; (IV) there is a nearby framework that is prestress stable, and thus rigid. The conditions can be tested efficiently using semidefinite programming. The test is a slight extension of the test for prestress stability of a framework, and gives analytic expressions for the radii of the balls and the edge length changes. Examples illustrate how the theory may be applied in practice, and we provide an algorithm to test for rigidity or almost-rigidity. We briefly discuss how the theory may be applied to tensegrities.
0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv
Linear Symmetries of the Unsquared Measurement Variety
We introduce a new family of algebraic varieties, $L_{d,n}$, which we call the unsquared measurement varieties. This family is parameterized by a number of points $n$ and a dimension $d$. These varieties arise naturally from problems in rigidity theory and distance geometry. In those applications, it can be useful to understand the group of linear automorphisms of $L_{d,n}$. Notably, a result of Regge implies that $L_{2,4}$ has an unexpected linear automorphism. In this paper, we give a complete characterization of the linear automorphisms of $L_{d,n}$ for all $n$ and $d$. We show, that apart from $L_{2,4}$ the unsquared measurement varieties have no unexpected automorphisms. Moreover, for $L_{2,4}$ we characterize the full automorphism group.
0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv
Packing Disks by Flipping and Flowing
We provide a new type of proof for the Koebe-Andreev-Thurston (KAT) planar circle packing theorem based on combinatorial edge-flips. In particular, we show that starting from a disk packing with a maximal planar contact graph $G$, one can remove any flippable edge $e^-$ of this graph and then continuously flow the disks in the plane, such that at the end of the flow, one obtains a new disk packing whose contact graph is the graph resulting from flipping the edge $e^-$ in $G$. This flow is parameterized by a single inversive distance.
0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv
A Report on Shape Deformation with a Stretching and Bending Energy
In this report we describe a mesh editing system that we implemented that uses a natural stretching and bending energy defined over smooth surfaces. As such, this energy behaves uniformly under various mesh resolutions. All of the elements of our approach already exist in the literature. We hope that our discussions of these energies helps to shed light on the behaviors of these methods and provides a unified discussion of these methods.
0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv
On the Embeddability of Delaunay Triangulations in Anisotropic, Normed, and Bregman Spaces
Given a two-dimensional space endowed with a divergence function that is convex in the first argument, continuously differentiable in the second, and satisfies suitable regularity conditions at Voronoi vertices, we show that orphan-freedom (the absence of disconnected Voronoi regions) is sufficient to ensure that Voronoi edges and vertices are also connected, and that the dual is a simple planar graph. We then prove that the straight-edge dual of an orphan-free Voronoi diagram (with sites as the first argument of the divergence) is always an embedded triangulation. Among the divergences covered by our proofs are Bregman divergences, anisotropic divergences, as well as all distances derived from strictly convex $\mathcal{C}^1$ norms (including the $L_p$ norms with $1< p < \infty$). While Bregman diagrams of the {first kind} are simply affine diagrams, and their duals ({weighted} Delaunay triangulations) are always embedded, we show that duals of orphan-free Bregman diagrams of the \emph{second kind} are always embedded.
0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv
Universal Rigidity of Complete Bipartite Graphs
We describe a very simple condition that is necessary for the universal rigidity of a complete bipartite framework $(K(n,m),p,q)$. This condition is also sufficient for universal rigidity under a variety of weak assumptions, such as general position. Even without any of these assumptions, in complete generality, we extend these ideas to obtain an efficient algorithm, based on a sequence of linear programs, that determines whether an input framework of a complete bipartite graph is universally rigid or not.
0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv
Low-level Vision by Consensus in a Spatial Hierarchy of Regions
We introduce a multi-scale framework for low-level vision, where the goal is estimating physical scene values from image data---such as depth from stereo image pairs. The framework uses a dense, overlapping set of image regions at multiple scales and a "local model," such as a slanted-plane model for stereo disparity, that is expected to be valid piecewise across the visual field. Estimation is cast as optimization over a dichotomous mixture of variables, simultaneously determining which regions are inliers with respect to the local model (binary variables) and the correct co-ordinates in the local model space for each inlying region (continuous variables). When the regions are organized into a multi-scale hierarchy, optimization can occur in an efficient and parallel architecture, where distributed computational units iteratively perform calculations and share information through sparse connections between parents and children. The framework performs well on a standard benchmark for binocular stereo, and it produces a distributional scene representation that is appropriate for combining with higher-level reasoning and other low-level cues.
0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv
Characterizing the universal rigidity of generic frameworks
A framework is a graph and a map from its vertices to E^d (for some d). A framework is universally rigid if any framework in any dimension with the same graph and edge lengths is a Euclidean image of it. We show that a generic universally rigid framework has a positive semi-definite stress matrix of maximal rank. Connelly showed that the existence of such a positive semi-definite stress matrix is sufficient for universal rigidity, so this provides a characterization of universal rigidity for generic frameworks. We also extend our argument to give a new result on the genericity of strict complementarity in semidefinite programming.
0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv
From Shading to Local Shape
We develop a framework for extracting a concise representation of the shape information available from diffuse shading in a small image patch. This produces a mid-level scene descriptor, comprised of local shape distributions that are inferred separately at every image patch across multiple scales. The framework is based on a quadratic representation of local shape that, in the absence of noise, has guarantees on recovering accurate local shape and lighting. And when noise is present, the inferred local shape distributions provide useful shape information without over-committing to any particular image explanation. These local shape distributions naturally encode the fact that some smooth diffuse regions are more informative than others, and they enable efficient and robust reconstruction of object-scale shape. Experimental results show that this approach to surface reconstruction compares well against the state-of-art on both synthetic images and captured photographs.
0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv
On affine rigidity
We define the notion of affine rigidity of a hypergraph and prove a variety of fundamental results for this notion. First, we show that affine rigidity can be determined by the rank of a specific matrix which implies that affine rigidity is a generic property of the hypergraph.Then we prove that if a graph is is $(d+1)$-vertex-connected, then it must be "generically neighborhood affinely rigid" in $d$-dimensional space. This implies that if a graph is $(d+1)$-vertex-connected then any generic framework of its squared graph must be universally rigid. Our results, and affine rigidity more generally, have natural applications in point registration and localization, as well as connections to manifold learning.
0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv
A geometrical approach to computing free energy landscapes from short-ranged potentials
Particles interacting with short-ranged potentials have attracted increasing interest, partly for their ability to model mesoscale systems such as colloids interacting via DNA or depletion. We consider the free energy landscape of such systems as the range of the potential goes to zero. In this limit, the landscape is entirely defined by geometrical manifolds, plus a single control parameter. These manifolds are fundamental objects that do not depend on the details of the interaction potential, and provide the starting point from which any quantity characterizing the system -- equilibrium or non-equilibrium -- can be computed for arbitrary potentials. To consider dynamical quantities we compute the asymptotic limit of the Fokker-Planck equation, and show that it becomes restricted to the low-dimensional manifolds connected by "sticky" boundary conditions. To illustrate our theory, we compute the low-dimensional manifolds for n<=8 identical particles, providing a complete description of the lowest-energy parts of the landscape including floppy modes with up to 2 internal degrees of freedom. The results can be directly tested on colloidal clusters. This limit is a novel approach for understanding energy landscapes, and our hope is that it can also provide insight into finite-range potentials.
0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv
Duals of Orphan-Free Anisotropic Voronoi Diagrams are Triangulations
We show that, under mild conditions on the underlying metric, duals of appropriately defined anisotropic Voronoi diagrams are embedded triangulations. Furthermore, they always triangulate the convex hull of the vertices, and have other properties that parallel those of ordinary Delaunay triangulations. These results apply to the duals of anisotropic Voronoi diagrams of any set of vertices, so long as the diagram is orphan-free.
0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv
Measurement Isomorphism of Graphs
The d-measurement set of a graph is its set of possible squared edge lengths over all d-dimensional embeddings. In this note, we define a new notion of graph isomorphism called d-measurement isomorphism. Two graphs are d-measurement isomorphic if there is agreement in their d-measurement sets. A natural question to ask is "what can be said about two graphs that are d-measurement isomorphic?" In this note, we show that this property coincides with the 2-isomorphism property studied by Whitney.
0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv
Orphan-Free Anisotropic Voronoi Diagrams
We describe conditions under which an appropriately-defined anisotropic Voronoi diagram of a set of sites in Euclidean space is guaranteed to be composed of connected cells in any number of dimensions. These conditions are natural for problems in optimization and approximation, and algorithms already exist to produce sets of sites that satisfy them.
0 citations0 reviewsNo code linkedOpen access