An optical disc records video objects that are obtained by multiplexing a video stream and an audio stream. The audio stream is an arrangement of a plurality of sets of audio frame data. Each video object unit in a video object is an arrangement of packs that have a different payload. The video stream and audio stream are divided using a predetermined size and the resulting data divisions are arranged into packs. At least one video object unit includes packs where stuffing bytes or a padding packet is arranged with part or all of a set of audio frame data so that the boundary with the next video object unit corresponds to a boundary between a boundary between sets of audio frame data. Since the boundary between video objects is made to match a boundary between sets of audio frame data, partial deletes that are performed with a video object unit as the smallest unit will not result in unnecessary parts of data remaining on the optical disc.