{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,4]],"date-time":"2022-04-04T22:35:22Z","timestamp":1649111722541},"reference-count":6,"publisher":"World Scientific Pub Co Pte Lt","issue":"05","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[2009,10]]},"abstract":"<jats:p> To calculate the Minkowski-sum based similarity measure of two convex polyhedra, many relative orientations have to be considered. These relative orientations are characterized by the fact that some faces and edges of the polyhedra are parallel. For every relative orientation of the polyhedra, the volume or mixed volume of their Minkowski sum is evaluated. From the minimum of this volume, the similarity measure is calculated. In this article two issues are addressed. First, we propose and test a method to reduce the set of relative orientations to be considered by using geometric inequalities in the slope diagrams of the polyhedra. In this way, the time complexity of O(n<jats:sup>6<\/jats:sup>) is reduced to O(n<jats:sup>4.5<\/jats:sup>). Secondly, we determine which relative orientation problems are ill-posed and may be skipped because they do not maximize the similarity measure. <\/jats:p>","DOI":"10.1142\/s0218195909003064","type":"journal-article","created":{"date-parts":[[2009,10,27]],"date-time":"2009-10-27T09:54:44Z","timestamp":1256637284000},"page":"441-456","source":"Crossref","is-referenced-by-count":1,"title":["REDUCING THE TIME COMPLEXITY AND IDENTIFYING ILL-POSED PROBLEM INSTANCES OF MINKOWSKI SUM BASED SIMILARITY CALCULATIONS"],"prefix":"10.1142","volume":"19","author":[{"given":"HENK","family":"BEKKER","sequence":"first","affiliation":[{"name":"Institute for Mathematics and Computing Science, University of Groningen, P.O.B. 800 9700 AV Groningen, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"AXEL A.","family":"BRINK","sequence":"additional","affiliation":[{"name":"Department of Artificial Intelligence, University of Groningen, P.O.B. 800 9700 AV Groningen, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"JOS B. T. M.","family":"ROERDINK","sequence":"additional","affiliation":[{"name":"Institute for Mathematics and Computing Science, University of Groningen, P.O.B. 800 9700 AV Groningen, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf1","first-page":"188","author":"Veltkamp R. C.","journal-title":"Shape Modeling International"},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1109\/34.713363"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1016\/S0031-3203(99)00159-4"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1023\/A:1013986402264"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1007\/BF00119839"},{"key":"rf8","volume-title":"Handbook of Convex Geometry","author":"Sangwine-Yager J. R.","year":"1993"}],"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218195909003064","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T00:24:25Z","timestamp":1565137465000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218195909003064"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,10]]},"references-count":6,"journal-issue":{"issue":"05","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2009,10]]}},"alternative-id":["10.1142\/S0218195909003064"],"URL":"https:\/\/doi.org\/10.1142\/s0218195909003064","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"value":"0218-1959","type":"print"},{"value":"1793-6357","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,10]]}}}