{"entities":{"Q1577545":{"pageid":1588285,"ns":120,"title":"Item:Q1577545","lastrevid":43221748,"modified":"2025-07-22T12:45:42Z","type":"item","id":"Q1577545","labels":{"en":{"language":"en","value":"Morphing simple polygons"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1495778"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1577545$63601A93-4C4D-4649-A99B-1876E14E46F9","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"02a7c218b03acf97a9b70e2605db1c2e72639b39","datavalue":{"value":{"text":"Morphing simple polygons","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1577545$4AB39171-409E-467B-96DD-B3CF5D31DB7C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7a0c48e4f74ecc4c1e3ff6d21791bd48827669c1","datavalue":{"value":"0968.68161","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1577545$4D08C834-2815-40EA-9176-F7163E530868","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"27055c7a0af767b1f36b14e7674bc0aa2224fdc0","datavalue":{"value":{"entity-type":"item","numeric-id":534491,"id":"Q534491"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1577545$98AD4A98-AA9D-4B34-B6D0-974DB0E6DBA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"94eab6fdb0a0437dc92c234ddacb5446e0f8992e","datavalue":{"value":{"entity-type":"item","numeric-id":1384195,"id":"Q1384195"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1577545$F3349DCF-0887-4BB6-88C0-4E5CB87051A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a13f3bebb56c4c4f5fc73ab576c62339f44d603f","datavalue":{"value":{"entity-type":"item","numeric-id":247185,"id":"Q247185"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1577545$147D4195-7796-4FDD-802B-5F3F2F3249BE","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b6f367138a9ac2b85113cfed5a6fd5bedcc8944c","datavalue":{"value":{"entity-type":"item","numeric-id":178842,"id":"Q178842"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1577545$F2746F58-1966-4BD2-8AE9-486EE0283AF0","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"88b3c329e48aa35406e35fc7c5218b06361eef1f","datavalue":{"value":{"time":"+2001-09-10T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1577545$602BC8DB-EBB5-473C-BD65-EBA7328532D0","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"650aceb74e75a9a26450cc27ad2dba6bddaa580b","datavalue":{"value":"Morphing two geometric shapes means finding a continuous deformation that transforms one shape into the other. This paper considers the problem of morphing two parallel simple polygons \\(P\\) and \\(Q\\) with \\(n\\) edges \\(P_i\\), \\(Q_i\\), \\(i=1,\\ldots,n\\), where edge \\(P_i\\) is parallel to edge \\(Q_i\\), and all intermediate shapes are also parallel simple polygons with \\(n\\) edges. The main result is an \\(O(n \\log n)\\) algorithm that determines for any such pair of simple polygons a morphing sequence of \\(O(n \\log n)\\) elementary transformations, i.e., uniform scalings or translations. This article builds upon the proceedings versions by \\textit{L. Guibas} and \\textit{J. Hershberger} [Proc. ACM Symp. Comp. Geom., 267-276 (1994)], and \\textit{J. Hershberger} and \\textit{S. Suri} [Morphing binary trees. In: Clarkson, K. (ed.), Proceedings of the 6th annual ACM-SIAM symposium on discrete algorithms, San Francisco, CA, USA, January 22-24, 1995. Philadelphia, PA, 396-404 (1995; Zbl 0849.68093)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q1577545$E67B7550-DA20-41DF-8176-624D723F98F4","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"159426a5937e62cfbbcc198dd4848ab52d6e715e","datavalue":{"value":"68U05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1577545$89CE2882-9ED2-4BE6-9A77-0DF0EDDC4847","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2f875a751d8a878059c157b8e38c948303fee90f","datavalue":{"value":"1495778","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1577545$9269EA0F-0483-4DEA-90B7-7C18541575D3","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"76439c3c7d8b7d13e1c15e65961d3443f0ea2b72","datavalue":{"value":"morphing","type":"string"},"datatype":"string"},"type":"statement","id":"Q1577545$869C0B2A-1BE3-4294-9018-C095094796C2","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"672ef8bc2e26406caa751faffd0b0ee75ec96a69","datavalue":{"value":{"entity-type":"item","numeric-id":169289,"id":"Q169289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1577545$9679CF0B-27CB-4059-8E10-2549E5286BF4","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1577545$5B3A9C75-FA6A-4C84-A074-DDF8D6CB23BB","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"29148f524f906577a54d82d19257e11e8952b282","datavalue":{"value":"https://doi.org/10.1007/s004540010017","type":"string"},"datatype":"url"},"type":"statement","id":"Q1577545$1B45069A-38C3-4EF6-8DB0-692B0746F503","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"d60f5ab264c2b9cd963705451c26e6cf5178498d","datavalue":{"value":"W1999074738","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1577545$A9C4C09A-D4A4-4277-870E-DFE236E0EB6C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ff1e3c846197ce6005c66f04954de296bb7f084a","datavalue":{"value":"10.1007/S004540010017","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1577545$B064A9F6-DF4E-45AC-892C-8F66215D6FE0","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d01b57c9851ed75aa365bd4d37112e5329366aa7","datavalue":{"value":{"entity-type":"item","numeric-id":2768363,"id":"Q2768363"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7a1bcdc3951aa31ac7ec38da55d0d512df076563","datavalue":{"value":{"amount":"+0.8871243","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1577545$B71449B7-56E0-4301-B07F-CB53D7584D3F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"31596c31ebc0dc9cacbee0d2cd5e20722a097021","datavalue":{"value":{"entity-type":"item","numeric-id":5505350,"id":"Q5505350"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a9cdfd55f205acee7559c5fac5a273f9e22273d1","datavalue":{"value":{"amount":"+0.87188566","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1577545$7436C444-A209-4CB5-993A-CFBE0FEF23A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"35ae8e56db73b927f35ef6994dac875c4728cbdd","datavalue":{"value":{"entity-type":"item","numeric-id":4923352,"id":"Q4923352"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1f971f091fe5728d17806fe9377d2aec872b3caf","datavalue":{"value":{"amount":"+0.8604655","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1577545$835A011A-F2A4-4927-A51F-96291925F8C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"deb098b627d0ca8b468c871a982fbe299cc76389","datavalue":{"value":{"entity-type":"item","numeric-id":5311633,"id":"Q5311633"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6650b4811f3dd7bd203be1144fd6b53f0f16b350","datavalue":{"value":{"amount":"+0.8545119","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1577545$8723C9B5-5169-41CF-9C86-5CE8972AEB28","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"84bc0e2ae879f5dce3db98c0f29f3fcd298ae5e3","datavalue":{"value":{"entity-type":"item","numeric-id":1603355,"id":"Q1603355"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fe933706e8fd351d139721919cdd69f2bddea3cc","datavalue":{"value":{"amount":"+0.8452596","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1577545$15EFE8D8-4A8B-4E4E-A88D-35ACC68C9DF5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"af688f34b5963e3f39ab596794018a757544c96c","datavalue":{"value":{"entity-type":"item","numeric-id":3379765,"id":"Q3379765"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6259d72aa8777d1780e99738102149e766f75d6b","datavalue":{"value":{"amount":"+0.8416544","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1577545$7A77B444-9BE8-477E-926F-6EB013C92B91","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6f57967fff7503af68cd2e6260e93a7f4badea34","datavalue":{"value":{"entity-type":"item","numeric-id":1205915,"id":"Q1205915"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b64abc7a80302f72ef46bc2629e1114fb3f6ace0","datavalue":{"value":{"amount":"+0.83902645","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1577545$D00283B9-AA8D-4DF5-BF51-E31727BC60A3","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1577545","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1577545"}}}}}