Dissemin is shutting down on January 1st, 2025

Published in

Elsevier, Artificial Intelligence, 1-2(105), p. 139-159, 1998

DOI: 10.1016/s0004-3702(98)00076-9

Links

Tools

Export citation

Search in Google Scholar

Detecting geometric infeasibility

Journal article published in 1998 by Achim Schweikard, Fabian Schwarzer
This paper is made freely available by the publisher.
This paper is made freely available by the publisher.

Full text: Download

Green circle
Preprint: archiving allowed
Upload
Orange circle
Postprint: archiving restricted
Upload
Red circle
Published version: archiving forbidden
Policy details
Data provided by SHERPA/RoMEO

Abstract

The problem of deciding whether one or more objects can be removed from a set of other planar or spatial objects arises in assembly planning, computer-aided design, robotics and pharmaceutical drug design. In this context, it will be shown that certain D-dimensional arrangements of hyperplanes can be analyzed in the following way: only a single connected component is traversed, and the arrangement is analyzed as an arrangement of surface patches rather than full hyperplanes. In special cases, this reduction allows for polynomial time bounds, even if the boundary of the set of reachable placements has exponential complexity. The described techniques provide the basis for an exact method for translational assembly planning with many degrees of freedom. Experiments obtained with an implementation suggest that problems with random planning methods, which are related to the choice of internal parameters can be avoided with this exact method. In addition, unsolvability can be established and the program can be applied to the verification of symbolic rules describing the geometry.