A Geometric Algorithm for Fault-Tolerant Classification of COVID-19 Infected People

摘要

As the world is struggling against COVID-19 pandemic, and unfortunately no certain treatments are discovered yet, prevention of further transmission by isolating infected people has become an effective strategy to overcome this outbreak. That is why scaling up COVID-19 testing is strongly recommended. However, depending on the time tests are performed, they may have a high rate of false-negative results. This inaccuracy of COVID-19 testing is a challenge against controlling the pandemic. Therefore, in this paper we propose a geometric classification algorithm that is fault-tolerant to handle the inaccuracy of tests. So, in a metropolis of n people, let w + r be the number of cases that are tested, where r is the number of positive, while w is the number of negative COVID-19 cases, and k is an upper bound on the number of false-negative COVID-19 cases. The proposed algorithm takes O(r • (log r + log w) + w^{3 + w log(hR)) time for isolating all positive cases together with at most k (according to the rate of error of testing) possibly positive (false-negative) cases from the rest of the people. The term hR in the time complexity is the size of convex hull of the set of positive cases, and obviously k ∈ O(w). For simplicity of this isolation, we consider a simple convex shape (a triangle) for this classification algorithm.}