{"entities":{"Q685601":{"pageid":687450,"ns":120,"title":"Item:Q685601","lastrevid":47189164,"modified":"2025-12-31T23:11:02Z","type":"item","id":"Q685601","labels":{"en":{"language":"en","value":"Linear-time algorithms for weakly-monotone polygons"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 417467"}},"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":"Q685601$2F52A5E2-C5CF-43DE-BE86-4D75BFF78561","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7b1769a680fa22d19f2625fba8cf2db06cc08827","datavalue":{"value":{"text":"Linear-time algorithms for weakly-monotone polygons","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q685601$7B9F26C2-59EA-4BA3-A3C5-0878C01F59EC","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"86cdba40dd87b00a7a975678b7177be30efaeb86","datavalue":{"value":"0792.68188","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685601$BAD72698-46D8-4530-A243-4F244606D05B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"be9fdaa23df73e646a9d2b63ff1214925e580d5b","datavalue":{"value":"10.1016/0925-7721(93)90031-Z","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685601$AC487907-772F-4141-B992-D625B65C10E9","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"0b10ce25f5ac1a5fb3c6dc1298c48041f4b1a4f5","datavalue":{"value":{"entity-type":"item","numeric-id":676581,"id":"Q676581"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685601$1EFAC14B-1EDC-4F6B-9A06-8C198C9B0411","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"285beb29e5e30a7ba8792191178d7f52682884ef","datavalue":{"value":{"entity-type":"item","numeric-id":175378,"id":"Q175378"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685601$3E15C24C-0AE7-43A2-B31E-BFFCDF26741D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"fcf8c05223362cb6bd6c445f68f31dd9aee8436e","datavalue":{"value":{"time":"+1994-08-07T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q685601$C359B938-5668-47D1-BDE9-C61686730FA4","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"970db06def50e9dbc2059954cc71634911320aa3","datavalue":{"value":"Triangulating a simple polygon is possible in linear time. But the corresponding algorithm is too complex to be considered practical. Simple optimal algorithms for special classes of polygons are interesting. The author studies a new class of so-called weakly-monotone polygons which contains the monotone class. The place in the hierarchy of simple polygons is discussed and a linear-time detection algorithm for the class is given. The author shows how to triangulate a weakly monotone polygon \\(P\\) in linear time, without prior knowledge of \\(P\\)'s weak-monotonicity. The algorithms are practical and conceptually simple.","type":"string"},"datatype":"string"},"type":"statement","id":"Q685601$54BCE303-4C0F-4FDC-A0FC-187F5AA1DC5A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"159426a5937e62cfbbcc198dd4848ab52d6e715e","datavalue":{"value":"68U05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685601$0F5C3968-E0C0-443D-9E9C-6DE109EA339B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685601$8073271B-9A63-49DB-862D-38522B2835B9","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8532c4d1e4deca4baf20441a3089ac8d2ae61329","datavalue":{"value":"417467","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685601$DEC0505A-9328-4236-AE14-41DEC6F687BD","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"596358b61297b80259e00b9995536e6529b13069","datavalue":{"value":"simple polygons","type":"string"},"datatype":"string"},"type":"statement","id":"Q685601$F2C2D08D-8D48-4C79-BCE2-A9A562ED9D82","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9bd3b97137fc5cddeb53bb49b8b441b42d47d65a","datavalue":{"value":"triangulation","type":"string"},"datatype":"string"},"type":"statement","id":"Q685601$C0EE887F-734F-43FE-B64C-678DE1304F66","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7250963987d7e4c99272889381793742a1498efc","datavalue":{"value":"linear-time algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q685601$D5A75914-8144-4564-948D-0D92D10B2F3F","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"f97401dc38cdab90e116741461a88db9a2626407","datavalue":{"value":{"entity-type":"item","numeric-id":701798,"id":"Q701798"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685601$A2B33E5E-7370-4E5E-B3D2-48CF5C720CB4","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":"Q685601$96DF1DFB-6598-49F3-8000-C7EE4D438EE7","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"8c6b6e839b5e54d44f9a88762c202a2f307fa9b7","datavalue":{"value":{"entity-type":"item","numeric-id":4024316,"id":"Q4024316"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685601$73CFCBEA-4EC6-4C8A-BA30-35E1BF5DDE84","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1527977d1e97f551ee80e9595c567d4fb5b3ce20","datavalue":{"value":{"entity-type":"item","numeric-id":1176324,"id":"Q1176324"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685601$CC113F5C-9186-428C-B540-0E9682E7B09A","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":"Q685601$A9974BB3-D08E-4E31-A619-A2A9E4285F72","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9adfe3a61d3a52386945e30186e12f90be5931bf","datavalue":{"value":{"entity-type":"item","numeric-id":911324,"id":"Q911324"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685601$28F66A94-9529-4C30-ABBD-EA9B124E5FE9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c179c216cda87e9f9cd3ed103ecfd568131908ef","datavalue":{"value":{"entity-type":"item","numeric-id":1118350,"id":"Q1118350"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685601$BED166D7-9BB4-4B3E-B4B6-F6F76B3506B1","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":"Q685601$63F43127-816E-4642-9598-DF8BDC7B3AED","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":"Q685601$6433BC7D-7076-4DEE-8D71-B9DF3422AB7A","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":"Q685601$430A6531-AD56-42A5-B5CA-6686642CCD0C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f3e4ab0d9c6453b2a26963b982b5c427c53ec041","datavalue":{"value":{"entity-type":"item","numeric-id":4188754,"id":"Q4188754"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685601$0CD9DFAB-4309-46F7-8205-1D2EA587C1FF","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b6818c0734845373adebf77bceab69dec722cefa","datavalue":{"value":{"entity-type":"item","numeric-id":3323307,"id":"Q3323307"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b1c197be4481d586256ed9241de72acb575571a7","datavalue":{"value":{"amount":"+0.8588892221450806","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":"Q685601$F37BA219-104A-4793-A2C3-0024EDAD0242","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"01aae63e382b88c58f0a5487b6b0cae3b93a4aec","datavalue":{"value":{"entity-type":"item","numeric-id":1176324,"id":"Q1176324"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f67d0678199b47d88fc5d84acdd4a3f5683f3fa7","datavalue":{"value":{"amount":"+0.8251436352729797","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":"Q685601$AD7E1DD8-8B8E-4816-AEE3-0ED14C4C31AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bc0c41c1f95f3cb58af7b33694395b732789f4e7","datavalue":{"value":{"entity-type":"item","numeric-id":1688854,"id":"Q1688854"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a05f3ed1a8f68469927cfe013a3b1e55436a3807","datavalue":{"value":{"amount":"+0.8098351955413818","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":"Q685601$158918C7-4AE2-4CFA-BC05-AFBC33619A3D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4bc3c13fdf6b816eec6028c07397f22eec760675","datavalue":{"value":{"entity-type":"item","numeric-id":1118350,"id":"Q1118350"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c480812a8db6d869d2d1da974c21e9d0109d26c7","datavalue":{"value":{"amount":"+0.8053916096687317","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":"Q685601$201ACBCD-6D62-45B7-991B-A7A39B6B1171","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c61b4b0f8e05c1beeef9beab09ccce16acb3d173","datavalue":{"value":{"entity-type":"item","numeric-id":3804191,"id":"Q3804191"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b52337baba15fd5a5f8ccc21f536a264bbec6330","datavalue":{"value":{"amount":"+0.8053368330001831","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":"Q685601$902783A7-A53D-4FF3-89FF-BD19280BD772","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:685601","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:685601"}}}}}