The directed Hausdorff distance between imprecise point sets

Details The directed Hausdorff distance between imprecise point sets The directed Hausdorff distance between imprecise point sets

2009-09-25

arxiv.org/abs/0909.4642v1

Computer Science

Computational Geometry

Scientific paper

We consider the directed Hausdorff distance between point sets in the plane, where one or both point sets consist of imprecise points. An imprecise point is modelled by a disc given by its centre and a radius. The actual position of an imprecise point may be anywhere within its disc. Due to the direction of the Hausdorff Distance and whether its tight upper or lower bound is computed there are several cases to consider. For every case we either show that the computation is NP-hard or we present an algorithm with a polynomial running time. Further we give several approximation algorithms for the hard cases and show that one of them cannot be approximated better than with factor 3, unless P=NP.

Affiliated with

Also associated with

No associations

Rating

The directed Hausdorff distance between imprecise point sets does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The directed Hausdorff distance between imprecise point sets, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The directed Hausdorff distance between imprecise point sets will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-325596