Minimum k-adjacent rectangles of orthogonal polygons and its application

Abstract : This paper presents the problem of partitioning a rectangle R which contains several non-overlapping orthogonal polygons, into a minimum number of rectangles. By introducing maximally horizontal line segments of largest total length, the number of rectangles intersecting with any vertical scan line over the interior surface of R is less than or equal to k, a positive integer. Our methods are based on a construction of the directed acyclic graph G = (V,E) corresponding to the structures of the orthogonal polygons contained in R. According to this, it is easy to verify whether a horizontal segment can be introduced in the partitioning process. It is demonstrated that an optimal partition exists if only if all path lengths from the source to the sink in G are less than or equal to k+1. Using this technique, we propose two integer program formulations with a linear number of constraints to find an optimal partition. Our goal is motivated by a problem involving utilization of memory descriptors applying to a memory protection mechanism for the embedded systems. We discuss our motivation in greater details.
Document type :
Conference papers
Complete list of metadatas

https://hal-cea.archives-ouvertes.fr/cea-01837010
Contributor : Léna Le Roy <>
Submitted on : Thursday, July 12, 2018 - 3:52:11 PM
Last modification on : Wednesday, January 23, 2019 - 2:39:33 PM

Identifiers

Collections

CEA | DRT | LIST

Citation

T.-H. Nguyen. Minimum k-adjacent rectangles of orthogonal polygons and its application. 2nd International Conference on Computer Science, Applied Mathematics and Applications, May 2014, Budapest, Hungary. pp.75-86, ⟨10.1007/978-3-319-06569-4_5⟩. ⟨cea-01837010⟩

Share

Metrics

Record views

51