BZPEERReading, trust and collaboration for researchDiscover
Workspaces
Network
Opportunities
Account
Researcher profile
Steven J. Gortler contributes to research discovery and scholarly infrastructure.
Trust snapshot
Actions
Identity and collaboration
Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.
Log in to claimDirect collaboration
Claim this author entity first to unlock direct invitations.
Research graph
Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
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.
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.
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.
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.
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.
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.