E-Book Overview
Tessellations are subdivisions of d-dimensional space into non-overlapping "cells". Voronoi tessellations are produced by first considering a set of points (known as nuclei) in d-space, and then defining cells as the set of points which are closest to each nuclei. A random Voronoi tessellation is produced by supposing that the location of each nuclei is determined by some random process. They provide models for many natural phenomena as diverse as the growth of crystals, the territories of animals, the development of regional market areas, and in subjects such as computational geometry and astrophysics. This volume provides an introduction to random Voronoi tessellations by presenting a survey of the main known results and the directions in which research is proceeding. Throughout the volume, mathematical and rigorous proofs are given making this essentially a self-contained account in which no background knowledge of the subject is assumed.
E-Book Content
Lecture Notes in Statistics Edited by S. Fienberg, J. Gani, K. Krickeberg, I. OIkin, and N. Wemmth 87 Jesper M~ller Lectures On Randolll Voronoi Tessellations Springer-Verlag New York Berlin Heidelberg London Paris Tokyo Hong Kong Barcelona Budapest Jesper M~ller Department of Theoretical Statistics Institute of Mathematics University of Aarhus DK-8000 Aarhus C DENMARK library of Congress Cataloging-in-Publication Data Mj'jller, Jesper. Lectures on random Voronoi tessellations 1J esper Mj'jller. p. em. -- (Lecture notes in statistics; 87) Includes bibliographical references and index. 1. Voronoi polygons. 2. Spatial analysis (Statistics). I. Title. II. Series: Lecture notes in statistics (Springer-Verlag); v. 87. QA278.2.M64 1994 133.9'01'3 -- dc20 94-248 Printed on acid-free paper. © 1994 Springer-Verlag New York, Inc. Softcover reprint of the hardcover Ist edition 1994 All rights reserved. This work may not be translated or copied in whole or in part without the written permission of the publisher (Springer-Verlag New York, Inc., 175 Fifth Avenue, New York, NY 10010, USA), except for brief excerpts in connection with reviews or scholarly analysis. Use in connection with any form of information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now known or hereafter developed is forbidden. The use of general descriptive names, trade names, trademarks, etc., in this publication, even if the former are not especially identified, is not to be taken as a sign that such names, as understood by the Trade Marks and Merchandise Marks Act, may accordingly be used freely by anyone. Camera ready copy provided by the author. 9 8 7 6 5 432 1 ISBN-13: 978-0-387-94264-3 DOl: 10.10071978-1-4612-2652-9 e-ISBN-13: 978-1-4612-2652-9 Editorial Policy for the publication of monographs In what follows all references to monographs are applicable also to multiauthorship volumes such as seminar notes. § 1. Lecture Notes aim to report new developments - quickly, informally, and at a high level. Monograph manuscripts should be reasonably self-contained and rounded off. Thus they may, and often will, present not only results of the author but also related work by other people. Furthermore, the manuscripts should provide sufficient motivation, examples, and applications. This clearly distinguishes Lecture Notes manuscripts from journal articles which normally are very concise. Articles intended for a journal but too long to be accepted by most journals, usually do not have this "lecture notes" character. For similar reasons it is unusual for Ph.D. theses to be accepted for the Lecture Notes series. § 2. Manuscripts or plans for Lecture Notes volumes should be submitted (preferably in duplicate) either to one of the series