{"entities":{"Q1705773":{"pageid":1716514,"ns":120,"title":"Item:Q1705773","lastrevid":68968950,"modified":"2026-04-13T03:26:16Z","type":"item","id":"Q1705773","labels":{"en":{"language":"en","value":"Covering points with convex sets of minimum size"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6851119"}},"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":"Q1705773$4CC3ECCD-AE42-4D2C-A1CC-785B1193340E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"649cc58b6b70d46956f0c27bb5fc6d6e61bea215","datavalue":{"value":{"text":"Covering points with convex sets of minimum size","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1705773$9DB3E32C-6C43-4EC4-AD12-8D544C99A977","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e9d1de26e834f79fd457198d19abe1556fe55eed","datavalue":{"value":"1395.68281","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1705773$3ACF0A92-36D3-4947-B5D3-9DC69601A18C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"aad2244a0fac49ecd6eb575ec97eea59fe9c09ce","datavalue":{"value":{"entity-type":"item","numeric-id":283874,"id":"Q283874"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1705773$2CC83652-2813-443E-ADB4-C7CD6ECC36F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"cd89bc9d013fa334e44ad843b6facf5c041dd909","datavalue":{"value":{"entity-type":"item","numeric-id":205081,"id":"Q205081"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1705773$7A5D4E32-EC62-4053-8581-CD2B6F71F319","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"9acec53c104fc0d98762859c57ff2f885c0ab7a5","datavalue":{"value":{"entity-type":"item","numeric-id":290510,"id":"Q290510"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1705773$3CC3B0AF-2A8F-47CB-A18D-F8C806F4F40A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c4035a96bb04f47aaa95450d00a0fa81814617f7","datavalue":{"value":{"entity-type":"item","numeric-id":824338,"id":"Q824338"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1705773$9A476A21-551F-45A1-8316-044E9DE6F7EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"fba8ae1f15f532d7104ee9a8930ec5ceaa2ea810","datavalue":{"value":{"entity-type":"item","numeric-id":216327,"id":"Q216327"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1705773$8C366E43-A9DE-4048-BADB-8ABEC08FADC6","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":"Q1705773$78568A6C-8F4B-4B94-BD88-7DE1573D6688","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"38a58aab6944d60b1cdbb1cc7c2901bec8dd645d","datavalue":{"value":{"time":"+2018-03-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1705773$2604373D-6962-4CD9-9EF6-D259AA7BBF3E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"4e4eeb099aea300d75e6106a627ccfb59200c577","datavalue":{"value":"In this paper algorithms are presented for finding two bounded convex sets, that cover a set \\(P\\) of \\(n\\) points in the plane, such that the total area or perimeter of the convex sets is minimized in \\(O(n^{4} \\log n)\\) and \\(O(n^{2} \\log n)\\) time, respectively. The former algorithm is the first result for minimum total area, and the latter one is an improvement on the fastest previous algorithm for minimum total perimeter, which runs in \\(O(n^{3})\\) time. Both presented algorithms are also extended to find \\(k \\geq 2\\) convex sets minimizing area in \\(O(n^{2k(k-1)} \\log n)\\) time. The proposed algorithms can be applied to detect road intersections from the GPS trajectories of moving vehicles for automated map generation or partial clustering.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1705773$72188ACE-A7F4-4102-8BFD-B4A0435A6441","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":"Q1705773$7F74443A-D1E4-4E67-B911-F5E7A05B0605","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"159426a5937e62cfbbcc198dd4848ab52d6e715e","datavalue":{"value":"68U05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1705773$31FBB26E-7736-4841-9517-62A273E413CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e5762e9b09407c15760c5fa5cac71c82c32bf230","datavalue":{"value":"52A10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1705773$06C42BDC-0283-495F-98F0-EE257D828D5C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2ce72165d993b0b8ed97728d731d2db2473b9554","datavalue":{"value":"65D18","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1705773$DE7FAF9A-CC87-4BAD-AC30-BDCAF28AEFC1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7ddaa80bf0a693a36c1113ff6b7ad576f729940","datavalue":{"value":"68W40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1705773$B5F84475-0671-4272-9365-8DA485D00FF0","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2623ed9fe242ea00464b6a9d526a8e20202d8ddf","datavalue":{"value":"6851119","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1705773$DBA97A94-B54E-4A09-8DF5-FF23BF58E609","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8d81fc6b606b1fdc546fa5c3be11c69913df3bff","datavalue":{"value":"covering points","type":"string"},"datatype":"string"},"type":"statement","id":"Q1705773$53572678-ED12-4B0C-8A3F-29A96ECFA21D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3465d3b553139c8fcbfcf785e2d6f309348aef38","datavalue":{"value":"convex sets","type":"string"},"datatype":"string"},"type":"statement","id":"Q1705773$C4376E13-0581-4724-91B6-01A46892AAAB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"87b147aa16e08aea71594b690e239b8aa358d8be","datavalue":{"value":"convex hulls","type":"string"},"datatype":"string"},"type":"statement","id":"Q1705773$97A8D29C-12D3-4F5F-A467-EA9176C307DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"62e6b80af768592f185fb3b451c535f4805ec94b","datavalue":{"value":"area","type":"string"},"datatype":"string"},"type":"statement","id":"Q1705773$A5916E45-0C35-4278-B7D0-B2255145F699","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"decce6156b96ab232aea36f0d02049bb64b638da","datavalue":{"value":"perimeter","type":"string"},"datatype":"string"},"type":"statement","id":"Q1705773$C5A63980-8F6D-4BB2-89F1-29A6A3ABDA19","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"551d108313cfab3a77b395a647aede7021169ebd","datavalue":{"value":"computational geometry","type":"string"},"datatype":"string"},"type":"statement","id":"Q1705773$0DB63D16-B272-45CD-A733-46C10E84E215","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":"Q1705773$7EB2DDB4-635F-4CB3-B08C-389A9F8CD6B8","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"550324472a7f048ebddc9b393bebd8ab8b93a064","datavalue":{"value":"https://doi.org/10.1016/j.tcs.2016.11.014","type":"string"},"datatype":"url"},"type":"statement","id":"Q1705773$C1C1A1D6-A241-44A8-9277-2A6F6D7962FF","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c42754c9affae41be5775982cede5ab45d62acde","datavalue":{"value":"W2549642977","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1705773$95C90643-B1E5-4FC0-84A5-B250A322D35C","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"c0db36da96ab01b8b34701dac13f356254faa8d3","datavalue":{"value":{"entity-type":"item","numeric-id":3201788,"id":"Q3201788"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1705773$234A4E36-9958-4B70-8EC4-D572F00B1E1F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1eb16790412e02703abbd98229c4b2bb240c2a41","datavalue":{"value":{"entity-type":"item","numeric-id":2912826,"id":"Q2912826"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1705773$B4E4D794-3695-4097-B6D3-04B81C766619","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7b90669c82727b021b133977c62f5b437aa17cda","datavalue":{"value":{"entity-type":"item","numeric-id":294806,"id":"Q294806"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1705773$DE7AF9EE-61D0-472D-8C2A-C5224D3D6F55","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c78500d6fcce07550315e59f9dcf0c342a2c4678","datavalue":{"value":{"entity-type":"item","numeric-id":3361924,"id":"Q3361924"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1705773$E248E6B6-B1F9-4235-ABFB-354B3E26FB4D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3a9c69e308d415a20025d0555b7fa5cf7a78db2c","datavalue":{"value":{"entity-type":"item","numeric-id":1961384,"id":"Q1961384"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1705773$7ADF12B2-62EF-45AD-B4AE-A162D1C0C0AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3fa24f136204d0dd2ccaf7987fe3c747f6025b88","datavalue":{"value":{"entity-type":"item","numeric-id":5417709,"id":"Q5417709"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1705773$7C610C99-9842-4A7E-9FC9-3E3BF2169D45","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8f2f85dc2559380394665c40e44da60d5990bdbd","datavalue":{"value":{"entity-type":"item","numeric-id":4763392,"id":"Q4763392"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1705773$CE9438BD-FDC6-48D7-BD5B-8524A3BE6B2E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"06bb2e50a70deee23cbf38ebcc3da4e0467bcd5e","datavalue":{"value":{"entity-type":"item","numeric-id":1186081,"id":"Q1186081"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1705773$E5175C4C-2881-4A84-B030-FDE16F93C8A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"db9edff5364d03929c45f7ea4f2a7f774baf55bc","datavalue":{"value":{"entity-type":"item","numeric-id":1917054,"id":"Q1917054"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1705773$00D27F44-3B27-43CF-8E58-AACEA8B6D0D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d5e8d03833a6c003c8590f31ec46fe8b8ba7831a","datavalue":{"value":{"entity-type":"item","numeric-id":1199831,"id":"Q1199831"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1705773$F336DB4F-CC97-49DE-86E6-DCD1163DE638","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"be4266d5bfbac7efe4beddc5935e50f3a034e546","datavalue":{"value":{"entity-type":"item","numeric-id":5406191,"id":"Q5406191"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1705773$9185FE19-08FB-43CB-B42F-7CA3D5EA57A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c549054e011690cdbe76aeada48482e9df7e10c2","datavalue":{"value":{"entity-type":"item","numeric-id":3348447,"id":"Q3348447"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1705773$47C0B8C4-121B-497C-B681-E2BB717D0A31","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d3bb34959889e000a68608d8eff8f84e68bfb906","datavalue":{"value":{"entity-type":"item","numeric-id":3089094,"id":"Q3089094"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1705773$0D2AD252-AE34-4A0E-BBE1-6BBB682998DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"02d8b11a73175a823902579bfd61977d87ac9c7e","datavalue":{"value":{"entity-type":"item","numeric-id":848964,"id":"Q848964"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1705773$97E53F19-FE61-4DE9-97E5-8492B1FD6EDA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8ae69f9da38de13449ee402c9adc52f1f8037b38","datavalue":{"value":{"entity-type":"item","numeric-id":4037420,"id":"Q4037420"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1705773$A2DFD6D2-0DA1-4115-B439-DF9369B5F851","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"99228cb4a4b649593a64ff8bf4966c7c6f44fd07","datavalue":{"value":{"entity-type":"item","numeric-id":2380042,"id":"Q2380042"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1705773$0E6D4F37-E71C-40E1-961F-C2C70A0D1809","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"86e140caef9645e724ad580b838166048edc608f","datavalue":{"value":{"entity-type":"item","numeric-id":989524,"id":"Q989524"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1705773$56E1192E-FF09-4D84-A3B5-9384FFD20AC4","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"636761affb174e81501f8ed96a0e4f32894f8d84","datavalue":{"value":"10.1016/J.TCS.2016.11.014","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1705773$E65840A9-647E-44A8-A1E3-410CB3101EBE","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"55f273031c33be29248af8fc60ede2f86a64f19b","datavalue":{"value":{"entity-type":"item","numeric-id":2803821,"id":"Q2803821"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cd70c958e427ccfd99fbb7713350673553d94ddc","datavalue":{"value":{"amount":"+0.9685038924217224","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":"Q1705773$9D3866D8-A3A1-4078-A19B-9DAD14BBFB21","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aa664907fbdaa5e2627c1aca3910166937ea9038","datavalue":{"value":{"entity-type":"item","numeric-id":283887,"id":"Q283887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f2e1b403c98b824a5c0054b5bab32960c292dfaa","datavalue":{"value":{"amount":"+0.7613682150840759","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":"Q1705773$1092B209-E673-46DA-A0C1-055ABF460BFC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ec40990574dfdc0b96b782c3706d78ea7b447a4f","datavalue":{"value":{"entity-type":"item","numeric-id":2428667,"id":"Q2428667"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"64ee65cb7124caa4545efb4082840c1cd1e6fd7c","datavalue":{"value":{"amount":"+0.743625819683075","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":"Q1705773$A811B7C1-714F-4EF1-B3D1-EDB118E243BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"57f7c4595aae3eac9c710c69cfa94c4f38c4ef87","datavalue":{"value":{"entity-type":"item","numeric-id":5757909,"id":"Q5757909"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"31b5fea74f926a2897bac60038973bd48cc94cc1","datavalue":{"value":{"amount":"+0.7434541583061218","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":"Q1705773$6A7C6746-CD7F-4B80-944C-E3E8FAC1BA3B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0acfb5fd1b1bd01f3e498981b6836ce42c8e76ad","datavalue":{"value":{"entity-type":"item","numeric-id":5233323,"id":"Q5233323"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ee561985e2b56a363822f30fd99081e8bdb9d350","datavalue":{"value":{"amount":"+0.7382891178131104","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":"Q1705773$FE6A9FB1-77DE-4B29-8BA6-0BC0D6605CEB","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Covering points with convex sets of minimum size","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Covering_points_with_convex_sets_of_minimum_size"}}}}}