Mapping Multiple Regions to the Grid with Bounded Hausdorff Distance
Publication date
2021
Authors
Hoog, Ivor van der
van de Kerkhof, Mees
van Kreveld, Marc
Löffler, M.
Staals, Frank
Urhausen, Jérôme
Vermeulen, Jordi
Editors
Lubiw, Anna
Salavatipour, Mohammad
He, Meng
Advisors
Supervisors
Document Type
Part of book
Metadata
Show full item recordCollections
License
taverne
Abstract
We study a problem motivated by digital geometry: given a set of disjoint geometric regions, assign each region Ri a set of grid cells Pi, so that Pi is connected, similar to Ri, and does not touch any grid cell assigned to another region. Similarity is measured using the Hausdorff distance. We analyze the achievable Hausdorff distance in terms of the number of input regions, and prove asymptotically tight bounds for several classes of input regions.
Keywords
Computational geometry, Digital geometry, Hausdorffdistance, Simple polygons, Taverne
Citation
van der Hoog, I, van de Kerkhof, M, van Kreveld, M, Löffler, M, Staals, F, Urhausen, J & Vermeulen, J 2021, Mapping Multiple Regions to the Grid with Bounded Hausdorff Distance. in A Lubiw, M Salavatipour & M He (eds), Algorithms and Data Structures : 17th International Symposium, WADS 2021, Virtual Event, August 9–11, 2021, Proceedings. 1 edn, Lecture Notes in Computer Science, vol. 12808, Springer, pp. 627-640. https://doi.org/10.1007/978-3-030-83508-8_45