{"entities":{"Q2000002":{"pageid":2010744,"ns":120,"title":"Item:Q2000002","lastrevid":57662109,"modified":"2026-03-31T20:11:23Z","type":"item","id":"Q2000002","labels":{"en":{"language":"en","value":"Capturing points with a rotating polygon (and a 3D extension)"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7074494"}},"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":"Q2000002$FA7B3E5A-21D1-4D87-BA0B-7BA02FA5204F","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"869fa0dee75d0e9d9991f3438b4a99ccc0704f21","datavalue":{"value":{"text":"Capturing points with a rotating polygon (and a 3D extension)","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2000002$8ABA8BE4-3403-4281-8F57-F538CAA6E6FA","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"44fb64783232919ce05ec8b58ab80e33c911bcea","datavalue":{"value":"1431.68113","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2000002$6F2BCD61-B5E4-460F-A3D5-BB72A8695029","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d114ab3761128c5ad6f60033ae5bc1cacaebf7bc","datavalue":{"value":{"entity-type":"item","numeric-id":1699298,"id":"Q1699298"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2000002$CBE79484-67BC-4E3F-89C0-EEF0DBBDE6B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"447795e8becd673565900ab5c09b008f43027e9a","datavalue":{"value":{"entity-type":"item","numeric-id":510535,"id":"Q510535"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2000002$CE432ED4-7CC7-4567-BB1F-0287031019F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"dc08bec4747515cd1e4f9ffbf99ef73fb0e278cf","datavalue":{"value":{"entity-type":"item","numeric-id":441870,"id":"Q441870"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2000002$5114EF55-36B9-4FE9-99CD-5D0749B69973","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e333b473062f409ce440a0394743f717fb6bbf5b","datavalue":{"value":{"entity-type":"item","numeric-id":170492,"id":"Q170492"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2000002$83F86187-B6C0-42F4-AA45-8B4B68E531BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c4c9be9ca23a2d959da50f0057a270a7fbc59409","datavalue":{"value":{"entity-type":"item","numeric-id":170450,"id":"Q170450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2000002$8ACD8628-6F32-4359-8D7E-EFB26D4EEE45","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b559743f011d61696dff04b2ecd3408df2541e49","datavalue":{"value":{"entity-type":"item","numeric-id":169698,"id":"Q169698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2000002$7EF53096-BAA0-4BB7-B227-B1B2C9EE8F22","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"34188037f8b0cd35688ae234ade090010846bddd","datavalue":{"value":{"time":"+2019-06-27T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2000002$ED8C3C43-0C54-4166-AF5D-442C05BD105F","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"035aa02fc8a1ee9c51b25c1fb9a9719e0838fc13","datavalue":{"value":"https://arxiv.org/abs/1805.02570","type":"string"},"datatype":"url"},"type":"statement","id":"Q2000002$FDD1FD0A-220D-4CE4-B9FE-E4FADE5B16F3","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"4cf0f1867d75d241098c93afa6966017aaaad80a","datavalue":{"value":"Rotation of an \\(n\\)-vertex simple polygon \\(P\\) around a fixed center to cover a maximum (or minimum) number out of \\(m\\)  given points of the plane is shown to be 3SUM-hard. A simple sweep over all critical angles  where some given point crosses an edge of \\(P\\) solves this problem in \\(O(nm\\log(nm))\\) time and \\(O(nm)\\) space. This complexity is often  improved by way of a moving radius sweep-circle maintaining its intersection with \\(P\\).  This latter idea  is then adapted to the extended problem where the rotation center may be moved along a segment, resulting in a plane-arrangement searchable for optimal depth, all of this in  \\(O(n^2m^2\\log(nm))\\) time and \\(O(n^2m^2)\\) space.  Finally, a method of this same complexity for the 3D version with fixed rotation center is outlined.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2000002$C6729116-3486-47F9-9577-DFCCDD5C1950","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"5e09f3da1a7483864918926ab5885138a8f45aaa","datavalue":{"value":{"entity-type":"item","numeric-id":166210,"id":"Q166210"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2000002$4E6A2EE6-9A86-41AB-8BF4-E866492153EC","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"159426a5937e62cfbbcc198dd4848ab52d6e715e","datavalue":{"value":"68U05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2000002$15F81112-BA0B-420C-98CD-34AE717E09DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2000002$EEBCF518-51B2-4697-993F-422187CA6664","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2000002$AC965F19-B2EF-42C3-8EA5-F8B64485300C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8c6278f15d25ee753aef3cc2e4a3cdfff50d9943","datavalue":{"value":"7074494","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2000002$37D7C2C7-E19D-4D8D-8ABE-BE099D479C0A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9c5042802b9b629f4407a45affe2829ec13eeb18","datavalue":{"value":"points covering","type":"string"},"datatype":"string"},"type":"statement","id":"Q2000002$D72C5A7D-5408-4CB4-8AD3-1FFC949BC842","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"086e460855e38352738b7bb2d98a987f7b4064c4","datavalue":{"value":"rotation","type":"string"},"datatype":"string"},"type":"statement","id":"Q2000002$119615A1-B3B6-4258-AD95-3E01944CD032","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0a2849fed3479edb812a736a871bd6b69ff9f050","datavalue":{"value":"geometric optimization","type":"string"},"datatype":"string"},"type":"statement","id":"Q2000002$CFE661A1-B045-495C-94B7-AE3E74467EED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5b198546508854bcc521c452e3e0681a16812ba9","datavalue":{"value":"polygon","type":"string"},"datatype":"string"},"type":"statement","id":"Q2000002$CF8CD157-73B3-4C19-93D2-ECD23D6AC5F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a9f2a96a2b64089759dd2d2593ced2328c88f9b6","datavalue":{"value":"polyhedron","type":"string"},"datatype":"string"},"type":"statement","id":"Q2000002$00BF57B1-1FC4-40B2-B706-821D7130C695","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b9ac296e5c659162f77b84948b588ef3272209b8","datavalue":{"value":"3SUM","type":"string"},"datatype":"string"},"type":"statement","id":"Q2000002$6CE5C841-B45C-40C7-A96F-5310DE10DEE3","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":"Q2000002$0DEBBD20-6CAB-4020-9E17-58A0141C55EE","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"6a52e3e5304c68bd97ed1c86177df42c610bd3a5","datavalue":{"value":"W3099711822","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2000002$4D284F35-0A5E-46FA-8405-686A18844833","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"13ef195c1c03f4b30fab65c7008258a73f1e01dd","datavalue":{"value":{"entity-type":"item","numeric-id":5959553,"id":"Q5959553"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2000002$6610002F-57BA-43D8-80B1-16C0DF72C36E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"846c278b89aa6a3e5dabbfdf5be62111b60c586c","datavalue":{"value":{"entity-type":"item","numeric-id":4411344,"id":"Q4411344"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2000002$8036341E-5EA1-4B0D-8479-1E8EDF2FFA42","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0455526de2067a10b78e3e612f6d0ede68e23659","datavalue":{"value":{"entity-type":"item","numeric-id":2482729,"id":"Q2482729"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2000002$9140C4B9-0186-4BD1-8DA7-4563A1F438FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"29c87897a15dd5154e873a4eb409b8f7e7be49d3","datavalue":{"value":{"entity-type":"item","numeric-id":2482905,"id":"Q2482905"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2000002$1055B39B-0B86-424B-AF7C-85FC3235E207","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4bd5c5eb92bb924c7c3460df4d724b831fc4e4fe","datavalue":{"value":{"entity-type":"item","numeric-id":390158,"id":"Q390158"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2000002$B8D8388D-2D4E-4915-9164-7DEB3F930E14","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"29e9c6f1c336326b447f12674867e9b56a9578af","datavalue":{"value":{"entity-type":"item","numeric-id":4682166,"id":"Q4682166"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2000002$3AFCB937-221B-4CFD-BA70-020312B9E4A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"652e91d772b0dd3c8a4ae08ed5ccd419710d7110","datavalue":{"value":{"entity-type":"item","numeric-id":1265324,"id":"Q1265324"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2000002$F2ABA97D-3DE5-4B2B-9F11-62B6F7152C7E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4f4ba771dac290a164052bbd8205a42e589a3f10","datavalue":{"value":{"entity-type":"item","numeric-id":1903639,"id":"Q1903639"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2000002$E732089B-914A-4D4B-8CB6-0F9AF928FFC4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fcd2a5820aca65bef19956320536cc56e9a9c3aa","datavalue":{"value":{"entity-type":"item","numeric-id":4561510,"id":"Q4561510"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2000002$54474BA6-D29B-4348-8A0B-53F13291B041","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"358bae9ccff0b01ba753556fcb9c8b9fd4148ea3","datavalue":{"value":{"entity-type":"item","numeric-id":4575670,"id":"Q4575670"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2000002$71F584AE-A9A7-466B-8D22-45C03912C2C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5bb899d5941f4ea62930a87bd9c20c70be3f808a","datavalue":{"value":{"entity-type":"item","numeric-id":2875187,"id":"Q2875187"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2000002$365CA2EB-3B21-4355-B43C-F38DEE5B192E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"5a7020a40ef4c8a3fd0e9af5dd08e3cd085718b8","datavalue":{"value":"10.1007/S00224-018-9885-Y","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2000002$ECCBC96C-25BC-4ED4-A6FC-EF8648FB2932","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"736b50b4dfda55d232780a463ee57f39cc1d60b1","datavalue":{"value":{"entity-type":"item","numeric-id":1265324,"id":"Q1265324"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7219ab0977fe9487d4d08cc045940712df78cf74","datavalue":{"value":{"amount":"+0.7931323051452637","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":"Q2000002$2C193B4F-51A0-4305-9175-FE14CE038BA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"961be16cf00ad0158f523569927d0ab5cc3c4cb0","datavalue":{"value":{"entity-type":"item","numeric-id":4875175,"id":"Q4875175"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"70c6444572b9d0a8a22bb23575ee8c11fb888906","datavalue":{"value":{"amount":"+0.7917741537094116","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":"Q2000002$85ABB2B6-A4D3-4ADA-A874-F69D89FDF4FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9d4ddd1dc2259b2c43d2e6c5b39133784a31504d","datavalue":{"value":{"entity-type":"item","numeric-id":2482905,"id":"Q2482905"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"66d70596a153511122da418c983023da2904e290","datavalue":{"value":{"amount":"+0.7766615152359009","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":"Q2000002$2B8323A5-5BDD-478D-9614-3FEBAD7EB602","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d78af2f0f850a4dd041ef90313cadc27d67414c2","datavalue":{"value":{"entity-type":"item","numeric-id":2477192,"id":"Q2477192"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"047fc658d26ca569c4681ad5e7332a61f739f359","datavalue":{"value":{"amount":"+0.7651291489601135","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":"Q2000002$97CCB0E1-FDC4-4ED6-9DF4-D79F372E0480","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4e2b50eb11c6ef2622a16b4c5e6694fb00d187ae","datavalue":{"value":{"entity-type":"item","numeric-id":1305861,"id":"Q1305861"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"53ab9695c664973f417efd8e992474765e19aa92","datavalue":{"value":{"amount":"+0.7349816560745239","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":"Q2000002$4BF458A5-3771-4C19-9D63-5EB4C107D484","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2000002","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2000002"}}}}}