Faithful Representation of a Family of Sets by a Set of Intervals
Kapali P. Eswaran · SIAM Journal on Computing · 1975
Let $Q = \{ q_1 ,q_2 , \cdots ,q_m \} $ be a family of finite, nonempty sets, and $S = \cup_{q_i \in Q} \{ q_i \} $. Suppose there exists a one-to-one function f that maps elements of S into points in the real line $\mathbb{R}$ such that for each $q_i \in Q$ there is an interval $I_i $ containing images of all elements of $q_i $ but not images of any elements not in $q_i $. Then the function f and the set of intervals $\{ I_1 ,I_2 , \cdots ,I_m \} $ are said to faithfully represent Q. Necessary and sufficient conditions and an algorithm for faithful representation of Q are developed. An important kind of file organization, called the consecutive retrieval file organization, is shown to be a direct application of the property of faithful representation.