Characterizing and covering some subclasses of orthogonal polygons Conference

Martins, AM, Bajuelos, AL. (2006). Characterizing and covering some subclasses of orthogonal polygons . EURO-PAR 2011 PARALLEL PROCESSING, PT 1, 3992 LNCS - II 255-262. 10.1007/11758525_34

cited authors

  • Martins, AM; Bajuelos, AL

authors

abstract

  • A grid n-ogon is a n-vertex orthogonal polygon that may be placed in a n/2 × n/2 unit square grid and that does not have collinear edges. Given a grid n-ogon P, let |∏(P)| be the number of rectangles that results when we partition P by extending the edges incident to reflex vertices towards its interior. P is called FAT if |∏(P)| is maximal for all grid n-ogons; P is called THIN if |∏(P)| is minimal for all grid n-ogons. THINS with area 2r+1 are called MIN-AREA. We will show that [n/6] vertex guards are necessary to guard a MIN-AREA grid n-ogon and present some problems related to THINS. © Springer-Vorlag Berlin Heidelberg 2000.

publication date

  • January 1, 2006

published in

Digital Object Identifier (DOI)

International Standard Book Number (ISBN) 10

International Standard Book Number (ISBN) 13

start page

  • 255

end page

  • 262

volume

  • 3992 LNCS - II