Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Hausdorff distance under translation for points and balls
Agarwal P., Har-Peled S., Sharir M., Wang Y. ACM Transactions on Algorithms6 (4):1-26,2010.Type:Article
Date Reviewed: Nov 18 2010

In the protein docking problem, pairs of molecules modeled as unions of balls are shape-matched by finding close but noncolliding positionings of the molecules. This provides one motivation for this work, which develops algorithms for four variations on finding the minimum Hausdorff distance under translation between two objects formed of unions of disks in 2 or balls in 3.

The variation for which the authors obtain the most complete results uses a Hausdorff distance where the balls are treated as objects themselves with their own natural atom-to-atom distance function, rather than as sets of points.

Here, they obtain exact algorithms with complexity Õ(n3) in 2 and Õ(n5) in 3 (where Õ ignores logarithmic factors) for n disks or balls. Their algorithms rely on combinatorial lemmas that support parametric search.

Treating the balls as sets of points leads to a rather different distance measure, for which they obtain the same complexity in 2, but must resort to approximation in 3, because of the lack of understanding of the Voronoi diagram of balls. They also obtain approximation algorithms for distance-function variants that are not as sensitive to outliers.

The authors leave as the main open problem extending their work from translation only to all rigid motions.

Reviewer:  Joseph O’Rourke Review #: CR138584 (1104-0419)
Bookmark and Share
  Featured Reviewer  
 
Pattern Matching (F.2.2 ... )
 
 
Biology And Genetics (J.3 ... )
 
 
Numerical Algorithms (G.1.0 ... )
 
 
Applications (G.1.10 )
 
 
Numerical Algorithms And Problems (F.2.1 )
 
Would you recommend this review?
yes
no
Other reviews under "Pattern Matching": Date
Deterministic sampling
Vishkin U. SIAM Journal on Computing 20(1): 22-40, 1991. Type: Article
Jun 1 1992
Two-way string-matching
Crochemore M., Perrin D. (ed) Journal of the ACM 38(3): 650-674, 1991. Type: Article
Sep 1 1992
On the exact complexity of string matching: lower bounds
Galil Z., Giancarlo R. SIAM Journal on Computing 20(6): 1008-1020, 1991. Type: Article
Jan 1 1993
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy