2013 | OriginalPaper | Buchkapitel
Verification Problem of Maximal Points under Uncertainty
verfasst von : George Charalambous, Michael Hoffmann
Erschienen in: Combinatorial Algorithms
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
The study of algorithms that handle imprecise input data for which precise data can be requested is an interesting area. In the
verification under uncertainty
setting, which is the focus of this paper, an algorithm is also given an assumed set of precise input data. The aim of the algorithm is to update the smallest set of input data such that if the updated input data is the same as the corresponding assumed input data, a solution can be calculated. We study this setting for the maximal point problem in two dimensions. Here there are three types of data, a set of points
P
= {
p
1
,…,
p
n
}, the uncertainty areas information consisting of
areas of uncertainty
A
i
for each 1 ≤
i
≤
n
, with
p
i
∈
A
i
, and the set of
P
′ = {
p
′
1
, . . . ,
p
′
k
} containing the assumed points, with
p
′
i
∈
A
i
. An
update
of an area
A
i
reveals the actual location of
p
i
and
verifies
the assumed location if
p
′
i
=
p
i
. The objective of an algorithm is to compute the smallest set of points with the property that, if the updates of these points verify the assumed data, the set of maximal points among
P
can be computed. We show that the maximal point verification problem is NP-hard, by a reduction from the minimum set cover problem.