Efficient distance computation using best ellipsoid fit

Author

Rimon, Elon ; Boyd, Stephen P.

Author_Institution

Stanford Univ., CA, USA

fYear

1992

fDate

11-13 Aug 1992

Firstpage

360

Lastpage

365

Abstract

The effectiveness of the ellipsoid representation for geometrical reasoning is demonstrated in the context of robotics. Specifically, a robot collision-detection problem that consists of computing a quantity that reflects, as a function of the geometrical data, the amount of clearance between the robot and its environment is discussed. The method consists of two algorithms. The first computes the optimal ellipsoid surrounding a convex polyhedron. The second computes an analytic formula for the free margin about one ellipsoid with respect to another, as a standard eigenvalue problem. An efficient incremental version of the latter algorithm is proposed. This system has been implemented, and preliminary simulation results are provided

Keywords

computational geometry; curve fitting; eigenvalues and eigenfunctions; robots; spatial reasoning; best ellipsoid fit; clearance; convex polyhedron; distance computation; eigenvalue; geometrical reasoning; robot collision-detection; Application software; Computational modeling; Computer science; Data structures; Eigenvalues and eigenfunctions; Ellipsoids; Information systems; Laboratories; Robots; Shape measurement;

fLanguage

English

Publisher

ieee

Conference_Titel

Intelligent Control, 1992., Proceedings of the 1992 IEEE International Symposium on

Conference_Location

Glasgow

ISSN

2158-9860

Print_ISBN

0-7803-0546-9

Type

conf

DOI

10.1109/ISIC.1992.225116

Filename

225116