Abstract
Assume that a set of imprecise points is given, where each point is specified by a region in which the point may lie. We study the problem of computing the smallest and largest possible tours and convex hulls, measured by length, and in the latter case also by area. Generally we assume the imprecision region to be a square, but we discuss the case where it is a segment or circle as well. We give polynomial time algorithms for several variants of this problem, ranging in running time from O(n) to O(n 13), and prove NP-hardness for some geometric problems on imprecise points.
This research was partially supported by the Netherlands Organisation for Scientific Research (NWO) through the BRICKS project GADGET and through the project GOGO.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Abellanas, M., Hurtado, F., Ramos, P.A.: Structural tolerance and Delaunay triangulation. Inf. Proc. Lett. 71, 221–227 (1999)
Bandyopadhyay, D., Snoeyink, J.: Almost-Delaunay simplices: nearest neighbour relations for imprecise points. In: Proc. 15th ACM-SIAM Sympos. on Discr. Algorithms, pp. 410–419 (2004)
Bajaj, C.: The algebraic degree of geometric optimization problems. Discr. Comput. Geom. 3, 177–191 (1988)
Boissonnat, J.-D., Lazard, S.: Convex hulls of bounded curvature. In: Proc. 8th Canad. Conf. on Comput. Geom., pp. 14–19 (1996)
Cai, L., Keil, J.M.: Computing visibility information in an inaccurate simple polygon. Internat. J. Comput. Geom. Appl. 7, 515–538 (1997)
de Berg, M., Meijer, H., Overmars, M.H., Wilfong, G.T.: Computing the angularity tolerance. Int. J. Comput. Geometry Appl. 8, 467–482 (1998)
Dror, M., Efrat, A., Lubiw, A., Mitchell, J.S.B.: Touring a Sequence of Polygons. In: Proc. 35th ACM Sympos. Theory Comput. (2003)
Edelsbrunner, H.: Finding transversals for sets of simple geometric figures. Theor. Comp. Science 35, 55–69 (1985)
Fiala, J., Kratochvil, J., Proskurowski, A.: Systems of distant representatives. Discrete Applied Mathematics 145, 306–316 (2005)
Goodrich, M.T., Snoeyink, J.: Stabbing parallel segments with a convex polygon. Computer Vision, Graphics, and Image Processing 49, 152–170 (1990)
Guibas, L., Salesin, D., Stolfi, J.: Constructing strongly convex approximate hulls with inaccurate primitives. Algorithmica 9, 534–560 (1993)
Khanban, A.A., Edalat, A.: Computing Delaunay triangulation with imprecise input data. In: Proc. 15th Canad. Conf. on Comput. Geom., pp. 94–97 (2003)
Löffler, M., van Kreveld, M.: Largest and Smallest Convex Hulls for Imprecise Points, Technical Report UU-CS-2006-019, Department of Computing and Information Science, Utrecht University (2006)
Löffler, M., van Kreveld, M.: Largest and Smallest Tours for Imprecise Points (manuscript, 2006)
Nagai, T., Tokura, N.: Tight error bounds of geometric problems on convex objects with imprecise coordinates. In: Jap. Conf. on Discrete and Comput. Geom., pp. 252–263 (2000)
Ostrovsky-Berman, Y., Joskowicz, L.: Uncertainty Envelopes. In: Abstracts 21st European Workshop on Comput., pp. 175–178 (2005)
Polishchuk, V., Mitchell, J.S.B.: Touring Convex Bodies - A Conic Programming Solution. In: Proc. 17th Canad. Conf. on Comput. Geom., pp. 290–293 (2005)
Sellen, J., Choi, J., Yap, C.-K.: Precision-sensitive Euclidean shortest paths in 3-space. SIAM J. Comput. 29, 1577–1595 (2000)
Yap, C.-K.: Robust geometric computation. In: Goodman, J.E., O’Rourke, J. (eds.) Handbook of Discrete and Computational Geometry, ch. 41, pp. 927–952. Chapman and Hall, Boca Raton (2004)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Löffler, M., van Kreveld, M. (2006). Largest and Smallest Tours and Convex Hulls for Imprecise Points. In: Arge, L., Freivalds, R. (eds) Algorithm Theory – SWAT 2006. SWAT 2006. Lecture Notes in Computer Science, vol 4059. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11785293_35
Download citation
DOI: https://doi.org/10.1007/11785293_35
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-35753-7
Online ISBN: 978-3-540-35755-1
eBook Packages: Computer ScienceComputer Science (R0)