{"entities":{"Q1762950":{"pageid":1773692,"ns":120,"title":"Item:Q1762950","lastrevid":68895042,"modified":"2026-04-13T02:57:17Z","type":"item","id":"Q1762950","labels":{"en":{"language":"en","value":"High-dimensional shape fitting in linear time"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2133697"}},"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":"Q1762950$D7DB52A3-B81F-4AC9-A6B7-5D3FC1242B6D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c252a26092c60ee066abf51d22f5555405a174fa","datavalue":{"value":{"text":"High-dimensional shape fitting in linear time","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1762950$C9952BF4-6D3C-44F0-A185-48CFC2769E5A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"92b6c29e0c44d50351d42cd443185d6e8e430ff4","datavalue":{"value":"1101.68909","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1762950$E39C3656-8D4B-4267-87E4-771AE91FA309","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"06885e4ccb9c846e3cd419bb7d9235a62bcac08f","datavalue":{"value":{"entity-type":"item","numeric-id":247175,"id":"Q247175"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1762950$F864EE48-F7C5-4BE4-9295-BEB858C471D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"cce85b4d0d7087c3d8e248a5cdb4c3b856fdb3b1","datavalue":{"value":{"entity-type":"item","numeric-id":590541,"id":"Q590541"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1762950$B1B08BC5-9358-427C-A62C-38C5DBC6A9A4","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":"Q1762950$5C787EE7-A34E-43F4-8300-76C690220A70","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5596d9d431c014306023aa27a7b00ce60a426d45","datavalue":{"value":{"time":"+2005-02-11T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1762950$7CEE8DCF-29A7-4538-A861-C78D8E260708","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c1e47829b6ba2f9397b93dfb88f6ae735947b173","datavalue":{"value":"Let \\(P\\) be a set of \\(n\\) points in \\(\\Re^d\\). The radius of a \\(k\\)-dimensional flat \\({\\mathcal F}\\) with respect to \\(P\\), which we denote by \\({\\mathcal RD}({\\mathcal F},P)\\), is defined to be \\(\\max_{p \\in P} \\text{dist}({\\mathcal F},p)\\), where \\(\\text{dist}({\\mathcal F},p)\\) denotes the Euclidean distance between \\(p\\) and its projection onto \\({\\mathcal F}\\). The \\(k\\)-flat radius of \\(P\\), which we denote by \\(R^{\\text{opt}_k}(P)\\), is the minimum, over all \\(k\\)-dimensional flats \\({\\mathcal F}\\), of \\({\\mathcal RD}({\\mathcal F},P)\\). We consider the problem of computing \\(R^{\\text{opt}_k}(P)\\) for a given set of points \\(P\\). We are interested in the high-dimensional case where \\(d\\) is a part of the input and not a constant. This problem is NP-hard even for \\(k = 1\\). We present an algorithm that, given \\(P\\) and a parameter \\(0 < \\varepsilon \\leq 1\\), returns a \\(k\\)-flat \\({\\mathcal F}\\) such that \\({\\mathcal RD}({\\mathcal F},P) \\leq (1 + \\varepsilon) R^{\\text{opt}_k}(P)\\). The algorithm runs in \\(O(nd C_{\\varepsilon,k})\\) time, where \\(C_{\\varepsilon,k}\\) is a constant that depends only on \\(\\varepsilon\\) and \\(k\\). Thus the algorithm runs in time linear in the size of the point set and is a substantial improvement over previous known algorithms, whose running time is of the order of \\(d n^{O(k/\\varepsilon^c)}\\), where \\(c\\) is an appropriate constant.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1762950$4A83E8D6-9367-4386-8429-535071E31476","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"159426a5937e62cfbbcc198dd4848ab52d6e715e","datavalue":{"value":"68U05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1762950$16BD336B-5972-4EC5-865A-E4CAEE12C844","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"79b3bc872b6637176b35f9e46ac855febbf884f5","datavalue":{"value":"68W05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1762950$9EF406D7-32FB-41C6-BE37-245F5655A1C8","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c9a66a2de958593ee00e6910a7eeecaf1e24aac4","datavalue":{"value":"2133697","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1762950$730A8564-F872-4B07-87D0-B56F59EE7F0B","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":"Q1762950$0D4BD9A5-2A4E-410C-95C2-9758AE3E77A7","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3dc8970862c51c3e889b2ec6215a0e56d00d969d","datavalue":{"value":"https://doi.org/10.1007/s00454-004-1118-2","type":"string"},"datatype":"url"},"type":"statement","id":"Q1762950$F3C57581-EDF2-4AA9-96A8-A86B9FD69F96","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"d529a3bef139470031c83769a4510034b31b81fa","datavalue":{"value":"W2093867071","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1762950$66590F27-59D1-4143-A26E-BB0B4DD1AF7D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"160bdc076b80332b18fd8925d642ec50555d23c1","datavalue":{"value":"10.1007/S00454-004-1118-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1762950$6D95834A-5011-4DF6-8A04-C9899FC69FC4","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"68409b9c503c86beca5143f57b4d51bf13f1a96f","datavalue":{"value":{"entity-type":"item","numeric-id":5361602,"id":"Q5361602"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1dc46660a5f61a39fe23b79fcf9ec8497afbe488","datavalue":{"value":{"amount":"+0.99999976","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1762950$5A4D7424-BFAF-4066-8514-2E1FB9EBD8F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"235fe4da95e23482beb037c98e3b119149b6dbff","datavalue":{"value":{"entity-type":"item","numeric-id":3639256,"id":"Q3639256"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ff55990cf626c63eb370ca057ff33470906006bb","datavalue":{"value":{"amount":"+0.8574587","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1762950$160D67A8-E6F1-4A26-BB46-FA7BD5D1073C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f19b669da2090c4ca2c7fd98aaf18d70638b7dc4","datavalue":{"value":{"entity-type":"item","numeric-id":6104071,"id":"Q6104071"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"390a37c6125356edd130be1ff8b320f91739fa85","datavalue":{"value":{"amount":"+0.8487825","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1762950$7D8C7228-5F3E-4176-9C47-A0CD711E9B65","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"707f80671839b6e56738287ae5913d0cc6d5094b","datavalue":{"value":{"entity-type":"item","numeric-id":2957523,"id":"Q2957523"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a9d85cfc03a17f50c339ec774f2858106ce947e5","datavalue":{"value":{"amount":"+0.84507614","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1762950$2D7E133C-C927-41B4-99D8-EE952CBEA245","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"362ec28135f9f77455d832afc3611b43ee5fc575","datavalue":{"value":{"entity-type":"item","numeric-id":3435602,"id":"Q3435602"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"091af24cb9528fa13b62cb274f524d17d15c80b6","datavalue":{"value":{"amount":"+0.842221","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1762950$ECFD59A4-62C5-4C17-AB30-E895C51F3739","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"163b2aa7b6c907211906e1a8fe11ce6e2cae5633","datavalue":{"value":{"entity-type":"item","numeric-id":4247400,"id":"Q4247400"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"782c4c1049d9aaf5357746a28e32e5e62c0c3f1b","datavalue":{"value":{"amount":"+0.84000695","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1762950$7FDD5FE9-5724-4A55-A985-1D94A1F6017A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7791d21c3f12f03c4a3ddf7f62394f10f8277d63","datavalue":{"value":{"entity-type":"item","numeric-id":4447312,"id":"Q4447312"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b6ff9684737f9daa8a0758ac6acde85f37fe70b2","datavalue":{"value":{"amount":"+0.83994174","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1762950$7D95BE7C-644D-4A9E-A012-71A8354512D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e3671eb801b448b0d52a0a42abe9821e81ba1961","datavalue":{"value":{"entity-type":"item","numeric-id":2345055,"id":"Q2345055"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d07fd8c5900b35012530e832552d3af796c490a5","datavalue":{"value":{"amount":"+0.8367237","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1762950$46C0D291-1EC8-469D-9F5D-76CF20343008","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bea6432986637b6f1f07cb2e5afcc5f517f5d509","datavalue":{"value":{"entity-type":"item","numeric-id":4808947,"id":"Q4808947"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6d7535bbd861d62d8a40820dd9a941c4114e9806","datavalue":{"value":{"amount":"+0.8367233","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1762950$030EADE8-FDA2-41F7-B342-7C9B684C4CC7","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"High-dimensional shape fitting in linear time","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/High-dimensional_shape_fitting_in_linear_time"}}}}}