1. A Compact Encoding of Plane Triangulations with Efficient Query Supports.
- Author
-
Hutchison, David, Kanade, Takeo, Kittler, Josef, Kleinberg, Jon M., Mattern, Friedemann, Mitchell, John C., Naor, Moni, Nierstrasz, Oscar, Pandu Rangan, C., Steffen, Bernhard, Sudan, Madhu, Terzopoulos, Demetri, Tygar, Doug, Vardi, Moshe Y., Weikum, Gerhard, Rahman, Md. Saidur, Yamanaka, Katsuhisa, and Nakano, Shin-ichi
- Abstract
In this paper we give a coding scheme for plane triangulations. The coding scheme is very simple, and needs only 6n bits for each plane triangulation with n vertices. Also with additional o(n) bits it supports adjacency, degree and clockwise neighbour queries in constant time. Our scheme is based on a realizer of a plane triangulation. The best known algorithm needs only 4.35n + o(n) bits for each plane triangulation, however, within o(n) bits it needs to store a complete list of all possible triangulations having at most (logn)/4 nodes, while our algorithm is simple and does not need such a list. The second best known algorithm needs 2m + (5 + 1/k)n + o(m + n) bits for each (general) plane graph with m edges and 7n + o(n) bits for each plane triangulation, while our algorithm needs only 6n + o(n) bits for each plane triangulation. [ABSTRACT FROM AUTHOR]
- Published
- 2008
- Full Text
- View/download PDF