Light field imaging enables a user to navigate and observe a static 3D scene from different viewpoints. Downloading the entire data prior to navigation would incur a large startup delay. Instead, previous works propose an interactive light field streaming (ILFS) framework, where a user periodically requests a viewpoint, and in response the server transmits a presynthesized and encoded viewpoint image. Using I-frame, P-frame and previously proposed merge frame that facilitates view-switches, the challenge is how to design and pre-encode a storage-constrained frame structure to enable efficient view navigation. In this paper, we initialize “landmarks” into a structure to improve ILFS performance. A landmark is a designated view with P-frames to/from each neighborhood view, so that any viewpoint image can transition to any other viewpoint image by first visiting a landmark, and then from the landmark to the destination view. This results in a transmission cost of only two P-frames. Using a Lloyd's algorithm variant, we first incrementally insert into a frame structure landmarks one at a time at locally optimal locations. We then employ a greedy algorithm to add / subtract P-frames based on a rate-storage criterion. Experimental results show that our proposed structures have noticeably lower expected transmission cost for the same storage than structures generated by a previous greedy algorithm.