Ranking Unit Squares with Few Visibilities

Simple item page
dc.creatorGärtner, Bernd
dc.date2008-07-14
dc.date.accessioned2026-07-07T09:50:11Z
dc.date.available2026-07-07T09:50:11Z
dc.descriptionGiven a set of n unit squares in the plane, the goal is to rank them in space in such a way that only few squares see each other vertically. We prove that ranking the squares according to the lexicographic order of their centers results in at most 3n-7 pairwise visibilities for n at least 4. We also show that this bound is best possible, by exhibiting a set of n squares with at least 3n-7 pairwise visibilities under any ranking.
dc.description4 pages, 2 EPS-figures
dc.identifierhttps://arxiv.org/abs/0807.2178
dc.identifierhttp://arxiv.org/abs/0807.2178
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/164857
dc.subjectComputational Geometry
dc.subjectData Structures and Algorithms
dc.titleRanking Unit Squares with Few Visibilities
dc.typetext

Files

Collections

arXiv