{"entities":{"Q688449":{"pageid":690298,"ns":120,"title":"Item:Q688449","lastrevid":63731193,"modified":"2026-04-11T15:09:58Z","type":"item","id":"Q688449","labels":{"en":{"language":"en","value":"Testing a simple polygon for monotonicity optimally in parallel"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 444835"}},"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":"Q688449$5C17B655-E767-437F-89D5-FA4683368549","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"32ebac8a8b99f28c22eeac0b570dee031a8168ee","datavalue":{"value":{"text":"Testing a simple polygon for monotonicity optimally in parallel","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q688449$2317065E-1C3F-4A4F-B2A9-85C1BB3B555A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ebc27f28fa8c87c9d9a83cb9f5a2ecd826cf01e1","datavalue":{"value":"0787.68100","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q688449$95D579C7-E0DF-4769-9664-9310D6E36D49","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8b33a8f5c87fed2e344678ac2779d1cb4688b99d","datavalue":{"value":"10.1016/0020-0190(93)90080-S","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q688449$A0CE4915-3034-47C7-81F8-788CD7497D28","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"45f6a7d29d05afbeef43db5dfb68629047eebcd1","datavalue":{"value":{"entity-type":"item","numeric-id":185435,"id":"Q185435"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688449$74E3A48D-E41B-451C-9532-C0AF169E7E33","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"96c78da18b20f136727359e09ae1bfef8c52cfbf","datavalue":{"value":{"entity-type":"item","numeric-id":688448,"id":"Q688448"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688449$AA41ABE8-9FA2-47DF-9610-18B48CC41520","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688449$761DF22B-80DA-4EFD-A31B-46D1CCB2CEAF","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7a2ae337094f9b29ef7d03c29f436d8f988b84f0","datavalue":{"value":{"time":"+1994-05-19T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q688449$476BFBCD-4BAC-43A9-B15E-A7D609B4E1A6","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"12a45fef0d91888a764014472bc2c7e3614aa1b5","datavalue":{"value":"We show that an \\(n\\)-vertex simple polygon can be tested in parallel for monotonicity optimally in \\(O(\\log n)\\) time using \\(n/\\log n\\) EREW PRAM processors, and we present two different optimal parallel algorithms for solving this problem.   Our results leads to an optimal parallel algorithm for triangulating simple polygons that runs in \\(O(\\log n)\\) time using \\(n/\\log n\\) EREW PRAM processors if the polygons are monotone.","type":"string"},"datatype":"string"},"type":"statement","id":"Q688449$2F2E50BC-C90C-4DC7-98FB-5EA4D67C4B05","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"159426a5937e62cfbbcc198dd4848ab52d6e715e","datavalue":{"value":"68U05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q688449$88F88CFD-1B6C-43A2-BE80-B6AD841A5FFA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b65efe51b183d0f4a672427b8171cd1e14211cba","datavalue":{"value":"68W15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q688449$28D5BE5D-B957-45C7-B1D5-2988C9D8479E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"07989db55613a02316da873cc3ca3afa8d03b9c1","datavalue":{"value":"444835","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q688449$2F4CC936-0FF0-4B95-B268-1718590F775C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d33669a46e6c8e8b36873d1f752821b7694a60c9","datavalue":{"value":"parallel algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q688449$29314149-1C5D-4343-8BF7-73ABA101815B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"551d108313cfab3a77b395a647aede7021169ebd","datavalue":{"value":"computational geometry","type":"string"},"datatype":"string"},"type":"statement","id":"Q688449$C89F59C8-CD7B-4F99-BDF9-DCE21969AB88","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"596358b61297b80259e00b9995536e6529b13069","datavalue":{"value":"simple polygons","type":"string"},"datatype":"string"},"type":"statement","id":"Q688449$940929F0-139F-4DE3-99BA-4F23C56EA6B4","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":"Q688449$882DBFA6-2986-462A-A2AF-9CB02CFA5D43","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"907c78ade0ae006b68f0f3b2942e05ac7e2ce5c7","datavalue":{"value":{"entity-type":"item","numeric-id":1123605,"id":"Q1123605"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688449$AEABE9E1-94D3-4867-ABB8-B7C4A060C355","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c7ea44918d9cd1c3450d92ce2807e95746d9a5b2","datavalue":{"value":{"entity-type":"item","numeric-id":3833604,"id":"Q3833604"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688449$7830E24E-B186-4397-A366-A3970774D6E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"77348396ef7ced333be21b7a2a15cdf427712110","datavalue":{"value":{"entity-type":"item","numeric-id":3833633,"id":"Q3833633"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688449$17FA605D-023D-4E3D-AEE2-C37DA59C3023","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bba9e98d83fb097641689563c120aebf958873f5","datavalue":{"value":{"entity-type":"item","numeric-id":3796769,"id":"Q3796769"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688449$7B83E440-90FD-4356-B6AC-24021EF571B0","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":"Q688449$3F377955-EB8F-4869-B942-E142054239BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"950f7d8f0a37d9b5618a6b1e082d7fa16ee38014","datavalue":{"value":{"entity-type":"item","numeric-id":4732108,"id":"Q4732108"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688449$37BB1E80-7EC4-4C34-A8A6-F8F9737FDD5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a65cef484c60240cbf9307e8d3c6d7ed99dce22e","datavalue":{"value":{"entity-type":"item","numeric-id":960516,"id":"Q960516"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688449$74808B61-7598-4AC4-816B-FD79B07E22C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c27205647ca572b79b66a603023449c3bc7df0f9","datavalue":{"value":{"entity-type":"item","numeric-id":582111,"id":"Q582111"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688449$A0EE7D44-5D9D-4E45-9EB8-21C616CB452F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"84bbca1bd52a8b705768d2a03b4b5b5c1b7c0d27","datavalue":{"value":{"entity-type":"item","numeric-id":4385522,"id":"Q4385522"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688449$81EFE504-E1C0-474C-A1A5-A7E4F392CD12","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"508894c78bd2770d073dbe57a0316a7e71f6bc30","datavalue":{"value":{"entity-type":"item","numeric-id":3890136,"id":"Q3890136"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688449$B2F6E630-304C-4004-8D95-50B877CCD3B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3367c340bcbab56184393a6f17fced2ae8ee934c","datavalue":{"value":{"entity-type":"item","numeric-id":3804191,"id":"Q3804191"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688449$D460DE7A-B176-4346-BD82-B698F3BCDFF5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ddcedef582459edc7492f134e78d6df36b1d2f6d","datavalue":{"value":{"entity-type":"item","numeric-id":1104087,"id":"Q1104087"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688449$96A89F44-4CFB-4ECC-9CDC-841FB984BAD9","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"70fe15caac7b2720e0470e17e8d0043ce1047dad","datavalue":{"value":"https://doi.org/10.1016/0020-0190(93)90080-s","type":"string"},"datatype":"url"},"type":"statement","id":"Q688449$EC3AE5B5-CF56-42DA-B15A-577C4709E969","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"1851a233396a0cf6240121a69f6834d00e6317e0","datavalue":{"value":"W2099794578","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q688449$A9E25079-0CD9-49EA-AE2C-ABB23AD5CC3D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c1862f053fa3ce15084c994f98f02b74c58a7e10","datavalue":{"value":{"entity-type":"item","numeric-id":3805897,"id":"Q3805897"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"16d3f4090b909a7fbc858d43373f6941d1017e43","datavalue":{"value":{"amount":"+0.8756093382835388","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":"Q688449$D3697EEA-99A0-492C-8E4C-BDC66D2C1B7E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7a99472b6e5de5401780652c6391e04ff17a85d1","datavalue":{"value":{"entity-type":"item","numeric-id":4732108,"id":"Q4732108"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4fc5a2503482ad1507f49d477baf9335165edd76","datavalue":{"value":{"amount":"+0.8521510362625122","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":"Q688449$7C96C6B8-5FD7-4429-BF5E-2A05121AA595","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8220b9a94a7278e7b8e54726f3feb97bbf86ff71","datavalue":{"value":{"entity-type":"item","numeric-id":1104087,"id":"Q1104087"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9692b198f5d93e72b936b45913df19f23756a598","datavalue":{"value":{"amount":"+0.822025716304779","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":"Q688449$3D7EC882-AE3F-403B-90D9-D1A5B92FFC64","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dc1855cb8f964de9b36ec5496bec83c021c14662","datavalue":{"value":{"entity-type":"item","numeric-id":4698354,"id":"Q4698354"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"24953edb679d2c1c120798cc996ba2e28f0b8c48","datavalue":{"value":{"amount":"+0.8101409077644348","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":"Q688449$CB0F98E0-DA4F-4B8A-84B5-7923225807BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6e74e164637468e87e4099ce2fac8356cc39b1eb","datavalue":{"value":{"entity-type":"item","numeric-id":4228433,"id":"Q4228433"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ac0b1590b252c7161525cebcb480cbee76390d7f","datavalue":{"value":{"amount":"+0.8014112114906311","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":"Q688449$52AB234D-593E-4D76-99E1-CDE1CDDEA098","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Testing a simple polygon for monotonicity optimally in parallel","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Testing_a_simple_polygon_for_monotonicity_optimally_in_parallel"}}}}}