{"entities":{"Q1176324":{"pageid":1187073,"ns":120,"title":"Item:Q1176324","lastrevid":66435006,"modified":"2026-04-12T10:03:23Z","type":"item","id":"Q1176324","labels":{"en":{"language":"en","value":"Triangulating a simple polygon in linear time"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 14030"}},"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":"Q1176324$FD84B2EF-1307-4380-B34D-485532A91AA1","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"de90e2897be496dd244be025bcda825d203c885b","datavalue":{"value":{"text":"Triangulating a simple polygon in linear time","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1176324$50AE2F9E-04E3-4C53-A036-DC3169BCAFBB","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"925fd7bf04b4e7fa2f3cd502cb8e23d69f5f6d90","datavalue":{"value":"0753.68090","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1176324$7E9D51DC-08D5-4AF4-9C5F-3DC2010B6083","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a8b5638c849e477c692dfc0fa132669cc0119c95","datavalue":{"value":"10.1007/BF02574703","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1176324$6B3E4132-D633-40CE-9843-C1BEB83CC12D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"5ad91bd4a1378a015ef9d0cfb2ca621b16347f71","datavalue":{"value":{"entity-type":"item","numeric-id":525971,"id":"Q525971"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1176324$7F6C8418-5B99-4208-8CC9-D6BD845A19D8","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":"Q1176324$3C7373EA-EE2A-4F5E-A5A1-3C5315970714","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d3f790682a6be4cc1f3210e15eebe1d6cc5ffbc2","datavalue":{"value":{"time":"+1992-06-25T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1176324$1DA43068-64E0-465E-9EA7-E822304517AA","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"319aca7be8b0a8cb6bb8c591aede051a4b0c7e39","datavalue":{"value":"https://eudml.org/doc/131172","type":"string"},"datatype":"url"},"type":"statement","id":"Q1176324$43DABB28-3EA1-43EE-99B3-FCCE01E00E2D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"7fb0bc109e722d7dd9d7e5d5cefc23547fb39dc1","datavalue":{"value":"The author gives an optimal linear time algorithm for triangulating on \\(n\\)-vertex simple polygon, thus a longstanding and basic open problem is settled. The underlying quite clear and intuitive ideas rely on the balanced divide and conquer, polygon cutting theorem and the plane separator theorem. However the full understanding of all details is a non-trivial task. In my opinion the step by step implementation is almost impossible in the present state of the algorithm.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1176324$D3C79C42-0370-490E-912F-EBB2E092C43D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"159426a5937e62cfbbcc198dd4848ab52d6e715e","datavalue":{"value":"68U05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1176324$5CBEE7C8-390E-4EF9-93BA-5957BAFBB79F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1176324$35B05AFD-27DB-49ED-873C-E6B6F7E2E244","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"275b97f971c35bf03725b2e21b4ef59e394fe8a9","datavalue":{"value":"14030","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1176324$2E0CD203-60C9-45DA-888B-88505262FC52","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9bd3b97137fc5cddeb53bb49b8b441b42d47d65a","datavalue":{"value":"triangulation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1176324$BF419F56-E7F9-4247-9040-49A31B17957D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ed28385b5c62eaaf3b0756eb74715fae1afa8293","datavalue":{"value":"simple polygon","type":"string"},"datatype":"string"},"type":"statement","id":"Q1176324$09EBAB2B-5475-4573-A37A-4AAA2B2F4CC4","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"532bbaac3e370e50bd6ddecca89db5cad8ecea04","datavalue":{"value":{"entity-type":"item","numeric-id":1071506,"id":"Q1071506"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1176324$BE0D6459-4DD9-4248-9C25-D334C2181CB7","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":"Q1176324$FDADEC8B-0FFF-4241-9D07-803A3B26E4E9","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"234f095244d8ea97ce870d264887d5435af58375","datavalue":{"value":"Q54156617","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1176324$BE4FE40F-F3B1-4975-BB24-D2B5E6FD5B11","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"4124ad3652fc359ba98d227348be70dfb6e4acf5","datavalue":{"value":{"entity-type":"item","numeric-id":910213,"id":"Q910213"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1176324$F9BEC03F-1648-4569-AE1F-182AB123B723","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a14bb5de49d1025f33147045f216b73559caa6b2","datavalue":{"value":{"entity-type":"item","numeric-id":3721846,"id":"Q3721846"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1176324$B3EE2CEE-2DB0-4BED-A17D-6CA1E72EE43E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"edb11b0dca7253830be5f8139bd13817d5fa1992","datavalue":{"value":{"entity-type":"item","numeric-id":1823686,"id":"Q1823686"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1176324$D2760A54-2F0E-4A00-AC99-71C43FB461A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f3fdde788538675a5d7d8479040594354c62d281","datavalue":{"value":{"entity-type":"item","numeric-id":1105375,"id":"Q1105375"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1176324$859C8694-06D8-43FA-BF4A-004BB3B26597","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e29b8e47936578f5cad24b50941e85f6a32ad9da","datavalue":{"value":{"entity-type":"item","numeric-id":3738618,"id":"Q3738618"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1176324$DA5A4E49-3248-4393-9F94-B6705D2FB013","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"83eade82042e507248d4b50c48d61d395faceaeb","datavalue":{"value":{"entity-type":"item","numeric-id":3358264,"id":"Q3358264"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1176324$B543A0E1-FB66-47EF-990F-0695B5055160","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6f0a1a2b9bf668daa897de5ce6a3be86456a7969","datavalue":{"value":{"entity-type":"item","numeric-id":3721847,"id":"Q3721847"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1176324$C3632E10-EBB5-4C23-9379-746B33EB6E99","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4ae0713540eb691df7bd8820bc004fcb597f484c","datavalue":{"value":{"entity-type":"item","numeric-id":1249042,"id":"Q1249042"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1176324$F8655F47-497E-4B97-877E-B257E463FBF7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"78ad3e344884042a22c9826d03bd0164d31b90d7","datavalue":{"value":{"entity-type":"item","numeric-id":1823689,"id":"Q1823689"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1176324$3AD805DD-C0BC-4F8A-8040-7BF29F4E544E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d2c6b273bbbfb23a71b64948d50760d60883087e","datavalue":{"value":{"entity-type":"item","numeric-id":1101226,"id":"Q1101226"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1176324$3EA1B2F5-EA44-4EBA-A822-D0C3D7A3A8CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6ff4e812fbcc008a1d5259e712cd9203d973f596","datavalue":{"value":{"entity-type":"item","numeric-id":3711764,"id":"Q3711764"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1176324$BAD729B7-D3B7-4BF9-9EA9-879B52578833","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d243ba8d0bd5b390703e3b0396162a69459086ca","datavalue":{"value":{"entity-type":"item","numeric-id":1114399,"id":"Q1114399"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1176324$85ADD003-39B4-430A-9CDE-64C2A5110728","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"60b12fa80e0883c7916ad7ebd37bad50bd07b508","datavalue":{"value":{"entity-type":"item","numeric-id":3670558,"id":"Q3670558"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1176324$08EC6DFA-A366-44CB-A489-6D936DE912AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d3b4f81716b6b99b3385ea9ee884bdf2887fe5b7","datavalue":{"value":{"entity-type":"item","numeric-id":4721658,"id":"Q4721658"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1176324$E493DB60-A975-4CC7-9548-D2ABE1185EFB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"813773fa16a57d5ba1f1f634d7f3bafad0c0476d","datavalue":{"value":{"entity-type":"item","numeric-id":3967063,"id":"Q3967063"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1176324$B728055A-6355-4C6F-AB17-C17993DD6968","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"51ff8a807471958a38eef5720fd27b64677c1d24","datavalue":{"value":{"entity-type":"item","numeric-id":3869371,"id":"Q3869371"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1176324$EAF3714B-500E-402F-8C92-7355BFBFA971","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1a2a57b475ae76d5a53ffe9b99df300f7fdeea33","datavalue":{"value":{"entity-type":"item","numeric-id":3906439,"id":"Q3906439"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1176324$FE7B3F96-0F3F-4145-B44D-C52A554B32AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"53270a197dc74dec5db368885ae5da2d9b50fbb5","datavalue":{"value":{"entity-type":"item","numeric-id":1253450,"id":"Q1253450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1176324$B936C4DC-3AFA-4563-A0BA-7BF93C4F0558","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a75892efb8c423df4e08c3a2522f9c8641bb850b","datavalue":{"value":{"entity-type":"item","numeric-id":3799261,"id":"Q3799261"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1176324$81D01DA6-5B0B-403F-AF75-5F9609A1B186","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a39eec153bd718a2c45744698baf06a8502d8bf9","datavalue":{"value":{"entity-type":"item","numeric-id":809630,"id":"Q809630"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1176324$F8CA9E45-DFDD-4F56-9EE0-9AE6E3EBBC9E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"45ce96ee513514e815725e851b3daeaea5391a2f","datavalue":{"value":{"entity-type":"item","numeric-id":3026389,"id":"Q3026389"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1176324$9EE89E39-8A6B-4434-88AF-761E3982958E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ac6746c85a669097b515fb2d37dce6f94b8ec7c0","datavalue":{"value":{"entity-type":"item","numeric-id":3777450,"id":"Q3777450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1176324$8324C001-A89C-4D1A-9CBE-AE6FE7742537","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"03e6a793829a78cf1632745f6762bdcf4eae7af6","datavalue":{"value":{"entity-type":"item","numeric-id":4040234,"id":"Q4040234"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1176324$52637A9F-2611-42AC-B2ED-C235FE7744B6","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"73d5fe48fcb9b51155c9c0d1c1c10826d2fa3c82","datavalue":{"value":{"entity-type":"item","numeric-id":1189285,"id":"Q1189285"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"92ddb924a7a74bcb4e5ee6ac717ac377a066938f","datavalue":{"value":{"amount":"+0.875213086605072","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":"Q1176324$B1DA8834-39BB-4D3F-8842-85F248E1E6B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fe164dd5535a7250ff9ccd7ed62c4522cb8bd0d2","datavalue":{"value":{"entity-type":"item","numeric-id":685601,"id":"Q685601"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1a36c8170e67809f6c1d018d798f65ba98222b62","datavalue":{"value":{"amount":"+0.8741886615753174","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":"Q1176324$0FBDDAB5-8FF8-4DA6-BFA9-652F95D9D519","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4ccd087bcc69ff4b38aaa13c81d6c63b2a517665","datavalue":{"value":{"entity-type":"item","numeric-id":3777450,"id":"Q3777450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3ea097f096fca49febe051a39cbe42151c03cb40","datavalue":{"value":{"amount":"+0.8684890866279602","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":"Q1176324$3FC23C52-B575-450A-86CC-C2E7C8C30D37","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7df7e1a6dacf38d69f52326f7b280c20f4dc4f16","datavalue":{"value":{"entity-type":"item","numeric-id":3721847,"id":"Q3721847"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f1643fb04c6aea1065d95cc13afd5cba97eebbde","datavalue":{"value":{"amount":"+0.8569781184196472","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":"Q1176324$68433089-D8B6-41AF-8C37-2B690A97323A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b57d75ee02a28b62542a0e0e89b7c3f0058e6cf5","datavalue":{"value":{"entity-type":"item","numeric-id":3721846,"id":"Q3721846"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bc42ef0559f2f460477054fc5f4bf90b8e8a43da","datavalue":{"value":{"amount":"+0.8523229360580444","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":"Q1176324$E44B5878-D61D-4812-A095-B6692169F00F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Triangulating a simple polygon in linear time","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Triangulating_a_simple_polygon_in_linear_time"}}}}}