Arrow Research search

Author name cluster

Brenda S. Baker

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
1 author row

Possible papers

9

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

FOCS Conference 1983 Conference Paper

An Algorithm for the Optimal Placement and Routing of a Circuit within a Ring of Pads (Extended Abstract)

  • Brenda S. Baker
  • Ron Y. Pinter

As the final stage in laying out a chip, the logic of the integrated circuit is assembled into one (not necessarily rectangular) module which must then be connected to pads lying along a rectangular frame. A placement for the module must be determined to assure the feasibility of the (river) routing from the logic inside to the pads on the periphery. We first show how to solve the routing problem in a stationary context: given the placement, can the signals be wired in the given doughnut-shaped area? Then we use the routability analysis developed in the first part to find a placement of the circuit that yields a feasible routing (if one exists). Both algorithms run in time that is quadratic in the size of the input, and there exist cases for which this bound cannot be improved upon.

Details

FOCS Conference 1983 Conference Paper

Approximation Algorithms for NP-Complete Problems on Planar Graphs (Preliminary Version)

  • Brenda S. Baker

This paper describes a general technique that can be used to obtain approximation algorithms for various NP-complete problems on planar graphs. The strategy depends on decomposing a planar graph into subgraphs of a form we call k- outerplanar. For fixed k, the problems of interest are solvable optimally in linear time on k-outerplanar graphs by dynamic programming. For general planar graphs, if the problem is a maximization problem, such as maximum independent set, this technique gives for each k a linear time algorithm that produces a solution whose size is at least (k-1)/k optimal. If the problem is a minimization problem, such as minimum vertex cover, it gives for each k a linear time algorithm that produces a solution whose size is at most (k + 1)/k optimal. Taking k = c log log n or k = c log n, where n is the number of nodes and c is some constant, we get polynomial time approximation schemes, i. e. algorithms whose solution sizes converge toward optimal as n increases. The class of problems for which this approach provides approximation schemes includes maximum independent set, maximum tile salvage, partition into triangles, maximum H-matching, minimum vertex cover, minimum dominating set, and minimum edge dominating set. For these and certain other problems, the proof of solvability on k-outerplanar graphs also enlarges the class of planar graphs for which the problems are known to be solvable.

Details
v2026.09.13