{"entities":{"Q1940704":{"pageid":1951446,"ns":120,"title":"Item:Q1940704","lastrevid":71182779,"modified":"2026-04-13T20:07:10Z","type":"item","id":"Q1940704","labels":{"en":{"language":"en","value":"An output-sensitive algorithm for persistent homology"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6142833"}},"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":"Q1940704$33A900BE-793B-4707-AD58-136453B9BD60","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c18ff223b0662b476a40bf4e69081b80bdf61771","datavalue":{"value":{"text":"An output-sensitive algorithm for persistent homology","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1940704$67B58F99-3F51-400B-91CB-84DEBC7BA494","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"9d4a24d8c737440c1eb11bed18593ce6cc4592d4","datavalue":{"value":"1264.65023","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1940704$79175CE7-21E2-4E56-ACA2-66DE1661E7EE","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"adc3f9c3986acb24c6667adbcd727f010b0b19ef","datavalue":{"value":{"entity-type":"item","numeric-id":291793,"id":"Q291793"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1940704$2E7249CE-4C4A-46BE-97BB-15E2CD2CBEAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"1de9a0f27e947037099f6eb0a97a5a7fc65d708c","datavalue":{"value":{"entity-type":"item","numeric-id":484889,"id":"Q484889"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1940704$D46F250E-6108-4496-BA6D-AF89C6F884B1","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":"Q1940704$61375A26-9B66-451A-8B03-5F36DB9E54FE","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3b19acb3e8c7a2662dfca6a9069f307fd3945628","datavalue":{"value":{"time":"+2013-03-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":"Q1940704$85FE2D44-DFCA-4809-B0C1-86BA6A1311DD","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"0d95b724e345c9aacc7e9f271de2a90cf18a5bcc","datavalue":{"value":"The authors study the computation of persistent homology of a simplicial complex over \\(\\mathbb Z_2\\). In this direction, the first algorithm by \\textit{H. Edelsbrunner} et al. [Discrete Comput. Geom. 28, No. 4, 511--533 (2002; Zbl 1011.68152)], was based on column-wise matrix reduction of a boundary matrix of the simplicial complex. The first output-sensitive analysis of an algorithm to compute a persistent homology that ignores homology classes of low persistence is presented here. Proposing a problem for further investigations, it is observed that although the authors' complexity results do not improve the worst-case time complexity of the problem, the approach of using state-of-the-art methods from symbolic computation can lead to more efficient algorithms.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1940704$7974433A-D942-42B4-96FA-A4FE97BCD231","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2ce72165d993b0b8ed97728d731d2db2473b9554","datavalue":{"value":"65D18","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1940704$7536C6F8-E013-4318-A2AD-456681C9276C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"355ea56a4f84d7973d94c70a8b1f92966ec83542","datavalue":{"value":"65Y20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1940704$F8A56155-8364-4C05-BA61-EC2D6F4AA7F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6be78f1bad1f2f19058dbde65eb124c0430a7d27","datavalue":{"value":"68W30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1940704$AEFAE0EE-91EA-40F6-9400-80AE9AAAC08E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d0325362351cc8c5a81e12db2c35614ce26c2351","datavalue":{"value":"6142833","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1940704$FC38760C-3ABC-4E56-B6CF-F588FCE325DA","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5e474a8987a98192748105597575b6fc52489a90","datavalue":{"value":"computational topology","type":"string"},"datatype":"string"},"type":"statement","id":"Q1940704$85085792-702E-4F89-868D-FC215EEEC69D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4f1d06f32b48414952aab32f07962f531328eb36","datavalue":{"value":"persistent homology","type":"string"},"datatype":"string"},"type":"statement","id":"Q1940704$D853B4CE-6DDF-4F29-A3EF-3F2314038D99","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"065dd7d355eb290e2c992ef117db17fe3396ae64","datavalue":{"value":"rank computation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1940704$4407647E-2CF4-4E31-B2F2-CF850507C246","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"466c3284448d1dda53576c5d0dd6ef79f5fe9aaa","datavalue":{"value":"worst-case time complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1940704$0EBF997E-CF27-43CA-A824-3C59DF7DDC09","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0e36fd2915ee69146bd208b73e1714d6ba9054ec","datavalue":{"value":"symbolic computation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1940704$53598B6C-F67A-46C3-9699-9D5472FF420E","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"956419f6fd71b8dac027f33d0ad5be15c64817eb","datavalue":{"value":{"entity-type":"item","numeric-id":182524,"id":"Q182524"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1940704$D4CD5288-C420-41E1-A715-9F9452BA34B4","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"c4fd57d313ed229e26f9f0606fa266058a6ffe6a","datavalue":{"value":{"entity-type":"item","numeric-id":13277,"id":"Q13277"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1940704$A772848D-7732-406F-9F65-5E070F8DD4BB","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":"Q1940704$F9301A13-64E5-4F26-A4D8-B479E1F04F98","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"7baa6dbd8c86620a85d0ff2753446bfd323494a9","datavalue":{"value":"https://doi.org/10.1016/j.comgeo.2012.02.010","type":"string"},"datatype":"url"},"type":"statement","id":"Q1940704$058B555C-8DF9-4E03-8D50-A0BE0521EA5A","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ebc2e8bb4789c7871e28040e61d4f9aae7ecf49f","datavalue":{"value":"W2207449046","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1940704$0037B412-C4A5-4E76-B7C9-2AF45E6ADC5F","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"cff34a54de771e04c511c088c336b6e4c8209914","datavalue":{"value":"Q59442775","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1940704$9E8B619E-C440-48C4-983F-F47136B47038","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"44a05c03478d4755bf682a91accdbe99303c70e7","datavalue":{"value":"10.1016/J.COMGEO.2012.02.010","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1940704$D36D2EFE-27B0-46DD-94FB-8FD59799CB01","rank":"normal"}],"P1635":[{"mainsnak":{"snaktype":"value","property":"P1635","hash":"56815f94dd5a052a7898b1da6a0b9e25bf7c5af5","datavalue":{"value":"journals/comgeo/ChenK13","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1940704$1E29B6FC-26F8-4C82-BDD0-4C5495F788C7","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5f9afd4fa3f1928202e3beba4b12633489d16f45","datavalue":{"value":{"entity-type":"item","numeric-id":5404426,"id":"Q5404426"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6f056cd81bfb0e436c14807ba87d928602c485f9","datavalue":{"value":{"amount":"+0.8619899153709412","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":"Q1940704$47E28561-BD3F-438A-B9CF-CEA4F5328BEB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b9bfa4adac1f821349590d7bef546c3265db69c3","datavalue":{"value":{"entity-type":"item","numeric-id":5361689,"id":"Q5361689"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e93a1ea52e720b40702706a42f79873a976776ea","datavalue":{"value":{"amount":"+0.8352950215339661","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":"Q1940704$1185605C-3D34-4CEB-B96B-542593FB7EC9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8d5a68740456e6822a1e27f7a6fa49a0b7e7b4ae","datavalue":{"value":{"entity-type":"item","numeric-id":1772133,"id":"Q1772133"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8e971c8b8867c74cfd3703182341e4a13bb96224","datavalue":{"value":{"amount":"+0.8194400668144226","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":"Q1940704$D3C1D55C-AF81-449A-9F89-B39F2281391E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f9210af188e36d63ed4ca159d870e5ce3aa27f9b","datavalue":{"value":{"entity-type":"item","numeric-id":5404427,"id":"Q5404427"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"24a0de0c337ec9848e9d8c3372c1350fa3792ab4","datavalue":{"value":{"amount":"+0.7950763702392578","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":"Q1940704$0AE9F37C-2F46-4789-BA40-FF391DAE9E86","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b206bdd702d47ea0d0e2496c203941b3e35f0077","datavalue":{"value":{"entity-type":"item","numeric-id":4635559,"id":"Q4635559"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a504af1d6fe262ff5c77efaf7ab7c1a40105e2c9","datavalue":{"value":{"amount":"+0.781696617603302","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":"Q1940704$CD00FCB7-83F5-48BA-9C53-925856F91DD5","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"An output-sensitive algorithm for persistent homology","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/An_output-sensitive_algorithm_for_persistent_homology"}}}}}