Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
In the Hausdorff Voronoi diagram of a set of point-clusters in the plane, the distance between a point t and a cluster P is measured as the maximum distance between t and any point in P, and the diagram reveals the nearest cluster to t. This diagram finds direct applications in VLSI computer-aided design. In this paper, we consider "non-crossing" clusters, for which the combinatorial complexity of the diagram is linear in the total number n of points on the convex hulls of all clusters. We present a randomized incremental construction, based on point-location, to compute the diagram in expected O(n log2 n) time and expected O(n) space, which considerably improves previous results. Our technique efficiently handles non-standard characteristics of generalized Voronoi diagrams, such as sites of non-constant complexity, sites that are not enclosed in their Voronoi regions, and empty Voronoi regions.
Язык оригинала | английский |
---|---|
Название основной публикации | LATIN 2014 |
Подзаголовок основной публикации | Theoretical Informatics - 11th Latin American Symposium, Proceedings |
Издатель | Springer Nature |
Страницы | 96-107 |
Число страниц | 12 |
ISBN (печатное издание) | 9783642544224 |
DOI | |
Состояние | Опубликовано - 1 янв 2014 |
Опубликовано для внешнего пользования | Да |
Событие | 11th Latin American Theoretical Informatics Symposium, LATIN 2014 - Montevideo, Уругвай Продолжительность: 31 мар 2014 → 4 апр 2014 |
Название | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
Том | 8392 LNCS |
ISSN (печатное издание) | 0302-9743 |
ISSN (электронное издание) | 1611-3349 |
конференция | 11th Latin American Theoretical Informatics Symposium, LATIN 2014 |
---|---|
Страна/Tерритория | Уругвай |
Город | Montevideo |
Период | 31/03/14 → 4/04/14 |
ID: 38614730