Arrow Research search

Author name cluster

Steven Fortune

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

9 papers
2 author rows

Possible papers

9

FOCS Conference 1989 Conference Paper

Stable Maintenance of Point Set Triangulations in Two Dimensions

  • Steven Fortune

Geometric algorithms are explored, assuming that arithmetic is done approximately. Stable algorithms are described for two geometric problems. The first algorithm computes two-dimensional convex hulls. The main result is that a triangulation of a set of points in the plane can be maintained stably. The second algorithm deals with line arrangements in the plane. >

Details

ICRA Conference 1986 Conference Paper

Coordinated motion of two robot arms

  • Steven Fortune
  • Gordon T. Wilfong
  • Chee-Keng Yap

We study the problem of planning simultaneous motion for two robot arms that are modeled on the Stanford arm. The arms have two degrees of freedom and must move in a workspace, avoiding obstacles and each other. We develop an O(n 2 logn) algorithm for planning motion of two arms with tips together, and an O(n 3 ) algorithm for independent but synchronized motion. Here n is the total number of walls of the obstacles.

Details

ICRA Conference 1985 Conference Paper

Stable prehension with a multi-fingered hand

  • Brenda S. Baker
  • Steven Fortune
  • Eric Grosse

We study grasps by a robot hand with three spring-loaded fingers. In two dimensions, the hand can grasp any polygon stably. That is, the grip is at a local minimum of the potential energy function defined by the springs of the fingers, ignoring friction. Surprisingly, under some conditions an equilibrium grasp on a circle is unstable even with respect to translation. In three dimensions, the hand can grasp and lift any cylindrical surface with a polygonal cross-section. In contrast we show that a hand with finger angles fixed at 120°, as proposed by Hanafusa and Asada, generally can not achieve a two-dimensional stable grip in the absence of friction.

Details

STOC Conference 1983 Conference Paper

Unbounded Fan-in Circuits and Associative Functions

  • Ashok K. Chandra
  • Steven Fortune
  • Richard J. Lipton

We consider the computation of finite semigroups using unbounded fan-in circuits. There are constant-depth, polynomial size circuits for semigroup product iff the semigroup does not contain a nontrivial group as a subset. In the case that the semigroup in fact does not contain a group, then for any primitive recursive function f , circuits of size O ( nf −1 ( n )) and constant depth exist for the semigroup product of n elements. The depth depends upon the choice of the primitive recursive function f . The circuits not only compute the semigroup product, but every prefix of the semigroup product. A consequence is that the same bounds apply for circuits computing the sum of two n -bit numbers.

Details

TCS Journal 1980 Journal Article

The directed subgraph homeomorphism problem

  • Steven Fortune
  • John Hopcroft
  • James Wyllie

The set of pattern graphs for which the fixed directed subgraph homeomorphism problem is NP-complete is characterized. A polynomial time algorithm is given for the remaining cases. The restricted problem where the input graph is a directed acyclic graph is in polynomial time for all pattern graphs and an algorithm is given.

Details DOI

STOC Conference 1978 Conference Paper

Parallelism in Random Access Machines

  • Steven Fortune
  • James Wyllie

A model of computation based on random access machines operating in parallel and sharing a common memory is presented. The computational power of this model is related to that of traditional models. In particular, deterministic parallel RAM's can accept in polynomial time exactly the sets accepted by polynomial tape bounded Turing machines; nondeterministic RAM's can accept in polynomial time exactly the sets accepted by nondeterministic exponential time bounded Turing machines. Similar results hold for other classes. The effect of limiting the size of the common memory is also considered.

Details
v2026.09.13