Note on the integer geometry of bitwise XOR

• Type: Article in International Scientific Journal
• Date: 2005

Authors

de Oliveira, AG (Author) FCUP; Silva, DOE (Author) Other

Journal

Title: European Journal of Combinatorics

Vol. 26

Pages: 755-763

ISSN: 0195-6698

Publisher: Elsevier

Indexing

ISI Web of Knowledge - 1 Citation

Scopus - 1 Citation

Scientific classification

FOS: Natural sciences > Mathematics

Other information

Authenticus ID: P-000-2H2

DOI: 10.1016/j.ejc.2004.02.008

Abstract (EN): We consider the set N of non-negative integers together with a distance d defined as follows: given two integers x, y is an element of N, d(x, y) is, in binary notation, the result of performing, digit by digit, the "XOR" operation on (the binary notations of) x and y. Dawson, in Combinatorial Mathematics VIII, Geelong, 1980, Lecture Notes in Mathematics, 884 (1981) 136, considers this geometry and suggests the following construction: given k different integers x(1),...,x(k) is an element of N, let V-i be the set of integers closer to x(i) than to any x(j) with j not equal i, for i, j = 1,...,k. Let V = (V-1,...,V-k) and X = (x(1),...,x(k)). V is a partition of {0, 1,...,2(n) - 1} which, in general, does not determine X. In this paper, we characterize the convex sets of this geometry: they are exactly the line segments. Given X and the partition V determined by X, we also characterize in easy terms the ordered sets Y = (y(1,)...,y(k)) that determine the same partition V. This, in particular, extends one of the main results of Combinatorial Mathematics VIII, Geelong, 1980, Lecture Notes in Mathematics, 884 (1981) 136.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 9