Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
Zur Ablage hinzufügen
  Lokale TagsFreigabegeschichteDetailsÜbersicht

Freigegeben
Forschungspapier

Embedding the Dual Complex of Hyper-rectangular Partitions

MPG-Autoren
/persons/resource/persons44759

Kerber,  Michael
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Externe Ressourcen
Es sind keine externen Ressourcen hinterlegt
Volltexte (beschränkter Zugriff)
Für Ihren IP-Bereich sind aktuell keine Volltexte freigegeben.
Volltexte (frei zugänglich)

arXiv:1207.3202.pdf
(Preprint), 369KB

Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

Kerber, M. (2013). Embedding the Dual Complex of Hyper-rectangular Partitions. Retrieved from http://arxiv.org/abs/1207.3202.


Zitierlink: https://hdl.handle.net/11858/00-001M-0000-0024-476A-3
Zusammenfassung
A rectangular partition is the partition of an (axis-aligned) rectangle into interior-disjoint rectangles. We ask whether a rectangular partition permits a "nice" drawing of its dual, that is, a straight-line embedding of it such that each dual vertex is placed into the rectangle that it represents. We show that deciding whether such a drawing exists is NP-complete. Moreover, we consider the drawing where a vertex is placed in the center of the represented rectangle and consider sufficient conditions for this drawing to be nice. This question is studied both in the plane and for the higher-dimensional generalization of rectangular partitions.