AN EFFICIENT METHOD TO DETERMINE THE INTENDED SOLUTION FOR A SYSTEM OF GEOMETRIC CONSTRAINTS
| Autor: | Hilderick A. van der Meiden, Willem F. Bronsvoort |
|---|---|
| Rok vydání: | 2005 |
| Předmět: |
Scheme (programming language)
Mathematical optimization Polynomial Selection (relational algebra) Relation (database) Backtracking Heuristic (computer science) Applied Mathematics CAD Theoretical Computer Science Constraint (information theory) Computational Mathematics Computational Theory and Mathematics Geometry and Topology computer Mathematics computer.programming_language |
| Zdroj: | International Journal of Computational Geometry & Applications. 15:279-298 |
| ISSN: | 1793-6357 0218-1959 |
| DOI: | 10.1142/s0218195905001701 |
| Popis: | The number of solutions of a geometric constraint problem is generally exponential to the number of geometric elements in the problem. Finding a single intended solution, satisfying additional criteria, typically results in an NP-complete problem. A prototype-based selection scheme is presented here that avoids this problem. First, a resemblance relation between configurations is formally defined. This relation should be satisfied between the intended solution and a prototype configuration. The resemblance relation is in our approach satisfied by applying selection rules to subproblems in a bottom-up solving approach. The resulting solving algorithm is polynomial, because the selection rules are not used as search heuristic, but to unambiguously select a single solution such that no backtracking search is needed. For many applications, in particular CAD, this solution is both meaningful and intuitive. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|