Given an unknown target planar map, we present an algorithm for constructing an approximation of the unknown target based on information gathered from linear probes of the target. Our algorithm is a general purpose reconstruction algorithm that can be applied in many settings. Our algorithm is particularly suited for the setting where computing the intersection of a line with an unknown target is much simpler than computing the unknown target itself. The algorithm maintains a triangulation from which the approximation of the unknown target can be extracted. We evaluate the quality of the approximation with respect to the target both in the topological sense and the metric sense. The correctness of the algorithm and the evaluation of its time complexity are also presented. Finally, we present some experimental results. For example, since generalized Voronoi diagrams are planar maps, our algorithm presents a simpler alternative method for constructing approximations of generalized Voronoi diagrams, which are notoriously difficult to compute.

Keywords:

References

F. Aurenhammer, ACM Comput. Surv. 23(3), 686 (1991), DOI: 10.1145/116873.116880. Google Scholar
F. Aurenhammer and R. Klein, Handbook of Computational Geometry, eds. J. R. Sack and J. Urrutia (Elsevier, 2000) pp. 201–290. Crossref, Google Scholar
G. Di Battista et al. , Graph Drawing: Algorithms for the Visualization of Graphs ( Prentice-Hall , 1999 ) . Google Scholar
I. Boada, N. Coll and J. A. Sellarès, The Voronoi-Quadtree: construction and visualization, Eurographics 2002 Short Presentation, Saarbruecken (Sep. 2002), pp. 349–355 . Google Scholar
I. Boada, N. Coll and J. A. Sellarès, Hierarchical planar Voronoi diagram approximations, Proc. 14th Canadian Conf. Computational Geometry (2002) pp. 40–45. Google Scholar
A. Bondy and U. Murty , Graph Theory with Applications ( North-Holland , 1976 ) , http://www.ecp6.jussieu.fr/pageperso/bondy/books/gtwa/gtwa.html . Crossref, Google Scholar
P. Bose and F. Hurtado, Flips in plane graphs, Technical Report 06-09, School of Computer Science, Carleton University (2006) . Google Scholar
P. Bose and G. Toussaint, J. Algorith. 19, 86 (1995), DOI: 10.1006/jagm.1995.1028. Crossref, Web of Science, Google Scholar
P. Bose and P. Morin, Theoret. Comput. Sci. 324(2-3), 273 (2004), DOI: 10.1016/j.tcs.2004.05.019. Crossref, Web of Science, Google Scholar
B. Chazelle, A theorem on polygon cutting with applications, Proc. IEEE Symp. Foundations of Computer Science (1982) pp. 339–349. Google Scholar
N. Coll, Approximation and visualization methods for bidimensional geometric objects, Ph.D. Thesis, Universitat Politècnica de Catalunya (2004) . Google Scholar
G. Dudek and M. Jenkin , Computational Principles of Mobile Robotics ( Cambridge University Press , 2000 ) . Google Scholar
R. Hartley and A. Zisserman , Multiple View Geometry in Computer Vision ( Cambridge University Press , 2000 ) . Google Scholar
K. Hoffet al., Fast computation of generalized Voronoi diagrams using graphics hardware, Proc. SIGGRAPH'99 (1999) pp. 277–286. Google Scholar
C. Ickinget al., On bisectors for different distance functions, Proc. 15th ACM Symp. Computational Geometry (1999) pp. 291–299. Google Scholar
D. Lavenderet al., IEEE Comput. Graph. Appl. 12(5), 69 (1992), DOI: 10.1109/38.156016. Crossref, Web of Science, Google Scholar
A. Okabe et al. , Spatial Tessellations: Concepts and Application of Voronoi Diagrams ( John Wiley & Sons , 2000 ) . Crossref, Google Scholar
L. A. Santaló , Integral Geometry and Geometric Probability ( Addison-Wesley , 1976 ) . Google Scholar
H. Solomon , Geometric Probability ( Society for Industrial and Applied Mathematics , 1978 ) . Crossref, Google Scholar
M. Teichmann and S. Teller, Polygonal approximation of Voronoi diagrams of a set of triangles in three dimensions, Technical Report 766, MIT Laboratory of Computer science (1997) . Google Scholar
G. Toussaint and D. Avis, Patt. Recogn. 15, 23 (1982), DOI: 10.1016/0031-3203(82)90057-7. Crossref, Web of Science, Google Scholar
J. Vleugels and M. Overmars, Int. J. Comput. Geom. Appl. 8, 201 (1998), DOI: 10.1142/S0218195998000114. Link, Web of Science, Google Scholar