{"entities":{"Q2192383":{"pageid":2203126,"ns":120,"title":"Item:Q2192383","lastrevid":57777141,"modified":"2026-04-02T11:58:29Z","type":"item","id":"Q2192383","labels":{"en":{"language":"en","value":"On compatible triangulations with a minimum number of Steiner points"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7235791"}},"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":"Q2192383$772B9D60-0B19-4E1F-A298-1816494E641D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2fa8247310e03f08d8a262d423cf9ffa9cbbd8cb","datavalue":{"value":{"text":"On compatible triangulations with a minimum number of Steiner points","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2192383$C8E04D84-0535-49C3-BB41-B277C35675FD","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"db80165f1260a1f9460c499740d97d15ae7865ed","datavalue":{"value":"1467.68199","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2192383$B7EC1BC6-16C5-4904-B3AF-6E6578212D6F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"938137206edfdd9a5ca2b52193c40f9e98ed806d","datavalue":{"value":{"entity-type":"item","numeric-id":293262,"id":"Q293262"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2192383$BDC31B5E-829A-4EC8-9592-46010CCD561D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b3b9cc1f159c37a4e5a1bbc7a4f2ae91d3150fc7","datavalue":{"value":{"entity-type":"item","numeric-id":396680,"id":"Q396680"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2192383$BCD83CE9-9EC1-4F77-86AB-C05CB59CAD5B","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2192383$7BE6A136-470F-401C-8F07-8526097755B3","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ec76352adfbb8538cfa6762a89b0767b3b568709","datavalue":{"value":{"time":"+2020-08-17T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2192383$2086730C-47C5-4A03-9F9B-36D993CBC82F","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ce18ddc2b8efb23c715d53ac539ea2f82210bf52","datavalue":{"value":"https://arxiv.org/abs/1706.09086","type":"string"},"datatype":"url"},"type":"statement","id":"Q2192383$748F4FDE-0453-4E39-ABCD-BBDCD1674E39","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"299461e2d950b644ac14307569b3ff3cf0ee5188","datavalue":{"value":"Compatible triangulations are used in computer graphics, e.g. in morphing. Two vertex-labelled polygons are compatible if they have the same clockwise cyclic ordering of vertices. This definition can be extended to polygonal regions and to triangulations. It is known that every pair of compatible \\(n\\)-vertex polygonal regions can be extended to compatible triangulations by adding the Steiner points. An intriguing open question is to decide if two compatible polygons have compatible triangulations with at most \\(k\\) Steiner points. In this paper it is proven that this problem is NP-hard for polygons with holes. For the other polygons this question still remains open.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2192383$3C98529E-FF71-49A6-9464-C03ED93C0D38","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"7e53786640a962176e9d0bea3688ff978e73b3e4","datavalue":{"value":{"entity-type":"item","numeric-id":305014,"id":"Q305014"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2192383$430E3F10-71B9-487B-A1A0-44FA6C21046C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"159426a5937e62cfbbcc198dd4848ab52d6e715e","datavalue":{"value":"68U05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2192383$67F89B73-FD46-4928-BE21-915009606839","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2192383$48B5A71A-CDDC-4ED7-A2EA-1F4FB089561E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"22d385cc8c410c96ab7b452335db1cfeff4ad213","datavalue":{"value":"7235791","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2192383$A52DA581-383A-468B-B785-54F820DBD6B6","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ada30e5d94dc0f32d330de70ca8b4cd707c9c398","datavalue":{"value":"polygonal regions","type":"string"},"datatype":"string"},"type":"statement","id":"Q2192383$3BC76293-79BA-49FF-BCEE-7B09A740A923","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"aafcde31c7b7a60a07ce1f3ff6e8cf16c059172e","datavalue":{"value":"compatible triangulations","type":"string"},"datatype":"string"},"type":"statement","id":"Q2192383$5A948E75-DF55-464F-B04C-2344B6EB0F91","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c7d5e4886aa4290eca104cd0d1da319d8b4d34c4","datavalue":{"value":"NP-hardness","type":"string"},"datatype":"string"},"type":"statement","id":"Q2192383$E45E5380-A91E-42D7-AC83-738BA9A6E5BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"642ecc893759bd431ee1d064c477c6e8566ce48d","datavalue":{"value":"linear homeomorphisms","type":"string"},"datatype":"string"},"type":"statement","id":"Q2192383$1B3FFF5B-62EB-4DFE-B361-6DA73718B66F","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":"Q2192383$7283FFD1-D34C-4B6C-A722-1D5F64361648","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"bb01832f34d48df6c156551f9c45a365a0ead7dd","datavalue":{"value":"W2962776977","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2192383$C69BD3CD-5003-4AEB-8542-FACCCEF86C00","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"87f6a1ff388e850ea93e4207f1d36b728df8e4e7","datavalue":{"value":{"entity-type":"item","numeric-id":1401254,"id":"Q1401254"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2192383$970CAA2B-66CC-4C68-A9CF-868FC3952BDC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"200b7fbadcdb8e6f3abb92d1da72c7b00d494e12","datavalue":{"value":{"entity-type":"item","numeric-id":5737811,"id":"Q5737811"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2192383$BF4B37DF-05F2-4307-8CB9-1D246AFA4D73","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"423a1a89aa638bfae0649e36b7f299edb548c1c2","datavalue":{"value":{"entity-type":"item","numeric-id":2367126,"id":"Q2367126"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2192383$AF39C377-EA2A-4A63-A278-D02A7E8220D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4c3271c2ceb737f33589e4b368a3fca419ca5f4a","datavalue":{"value":{"entity-type":"item","numeric-id":5899628,"id":"Q5899628"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2192383$4F084A8A-9E87-4297-855F-74BF8F1B1167","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"02dfe49b0bf0fd99001055257dd5894a4b402d25","datavalue":{"value":{"entity-type":"item","numeric-id":5299997,"id":"Q5299997"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2192383$0EEC116D-C254-47D4-ADB7-DC624C2C8DB1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0e78d5f14a77366d5339f5e832ab3aad1a4b07b5","datavalue":{"value":{"entity-type":"item","numeric-id":3580937,"id":"Q3580937"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2192383$28E7CD3E-730B-4BE2-946D-1D46379DC0A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ca9f06079288375b02717705824a66f29c87a5dd","datavalue":{"value":{"entity-type":"item","numeric-id":5712142,"id":"Q5712142"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2192383$FFC49EA8-A8EC-4641-93C3-533AD8F38FDB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fb891f09bc44a6ed29e70706730b432221d991f9","datavalue":{"value":{"entity-type":"item","numeric-id":4513241,"id":"Q4513241"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2192383$BD83C7CA-C607-4D0B-9A64-2C45752E74D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d5210e7c69ae3f2b00452e25f5f883d33fb7bf00","datavalue":{"value":{"entity-type":"item","numeric-id":1725774,"id":"Q1725774"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2192383$83F2563E-2249-4297-AF9F-CEC2034814E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1b15bc2894d3c3113990f2df75e823aff547e107","datavalue":{"value":{"entity-type":"item","numeric-id":1920423,"id":"Q1920423"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2192383$DFC95D01-DB52-4430-9B00-19A5256906D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"42f6ebffc6dfebeee4d60b1b3e56a7cfe848a67e","datavalue":{"value":{"entity-type":"item","numeric-id":5956107,"id":"Q5956107"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2192383$3E30FDBE-194C-4404-8AF4-63E7E2A2C627","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c032cb577bd8adc2219cd3cb9b006cd448562fdf","datavalue":{"value":{"entity-type":"item","numeric-id":3557891,"id":"Q3557891"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2192383$F2357B61-09F3-4064-8186-479111FD2DD1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"14d65f813b7bf62e89eaf2eb886e2ecf258499df","datavalue":{"value":{"entity-type":"item","numeric-id":4221106,"id":"Q4221106"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2192383$FDE1C463-3B66-4DAF-A573-C80AA5FC566D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8b98cad52573782f3076ab20acaae73b85968e5c","datavalue":{"value":{"entity-type":"item","numeric-id":595673,"id":"Q595673"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2192383$90EAEEB4-D6F7-4F5A-882C-22457161756A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"51374d7a37b6be5907f3ce9bc300448185ac6b85","datavalue":{"value":"10.1016/J.TCS.2020.06.014","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2192383$C6EBC2EA-F34A-461D-AEEE-C199F5A1BB73","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"177106ff25d37c65a925e522c9970badeed24a12","datavalue":{"value":{"entity-type":"item","numeric-id":2367126,"id":"Q2367126"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"aeeadbd446e3871f213b4d6dc46694c50116a1d1","datavalue":{"value":{"amount":"+0.8396293520927429","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2192383$EEF7E8D1-2378-49FF-972D-DBEE9CDFF79E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"46c85e404e95f44c097548b429a09cd472647ec8","datavalue":{"value":{"entity-type":"item","numeric-id":906837,"id":"Q906837"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a27232aeaa28876ec4991ce83c61a010c08184df","datavalue":{"value":{"amount":"+0.8378909230232239","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2192383$2EA9E552-2D4B-4EE9-AD48-9108C94FF3F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"55ab45f99f2c331e5dc45b31693721b6c9d1ae86","datavalue":{"value":{"entity-type":"item","numeric-id":4551352,"id":"Q4551352"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"aab43ccb487c4694f852e6d91b1e70f7f2a05382","datavalue":{"value":{"amount":"+0.833265483379364","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2192383$D8375CAF-D0E5-4519-B530-0B708C8E847D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f4a25922f8db0617e360e7874c12fde24eb322bf","datavalue":{"value":{"entity-type":"item","numeric-id":1401254,"id":"Q1401254"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"db7e12a2c196f528321101c0f1f1d9243bf25eb2","datavalue":{"value":{"amount":"+0.8037557601928711","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2192383$C1099C3B-90E9-4030-814D-B56ECB253571","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a05162eb3675891f99b17c5fe1c66b0a4612dda4","datavalue":{"value":{"entity-type":"item","numeric-id":2495951,"id":"Q2495951"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"582f46655aaf78d3700deaf70f10ba09b573cebf","datavalue":{"value":{"amount":"+0.8024404048919678","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2192383$A3042549-5C9C-4E77-A960-CAD0A54926BE","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2192383","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2192383"}}}}}