Cover Image

Deletion in Abstract Voronoi Diagrams in Expected Linear Time and Related Problems

CC BY

Saved in:
Bibliographic Details
Main Authors: Kolja, Junginger, Evanthia, Papadopoulou
Format: Book
Language:English
Published: Springer 2023
Subjects:
Voronoi diagram
Voronoi-like diagrams
Online Access:https://link.springer.com/article/10.1007/s00454-022-00463-z
https://dlib.phenikaa-uni.edu.vn/handle/PNK/7523
Tags: Add Tag
No Tags, Be the first to tag this record!
id oai:localhost:PNK-7523
record_format dspace
spelling oai:localhost:PNK-75232023-04-05T02:17:16Z Deletion in Abstract Voronoi Diagrams in Expected Linear Time and Related Problems Kolja, Junginger Evanthia, Papadopoulou Voronoi diagram Voronoi-like diagrams CC BY Updating an abstract Voronoi diagram in linear time, after deletion of one site, has been an open problem in a long time; similarly, for any concrete Voronoi diagram of generalized (non-point) sites. In this paper we present a simple, expected linear-time algorithm to update an abstract Voronoi diagram after deletion of one site. To achieve this result, we use the concept of a Voronoi-like diagram, a relaxed Voronoi structure of independent interest. Voronoi-like diagrams serve as intermediate structures, which are considerably simpler to compute, thus, making an expected linear-time construction possible. 2023-04-05T02:17:16Z 2023-04-05T02:17:16Z 2023 Book https://link.springer.com/article/10.1007/s00454-022-00463-z https://dlib.phenikaa-uni.edu.vn/handle/PNK/7523 en application/pdf Springer
institution Digital Phenikaa
collection Digital Phenikaa
language English
topic Voronoi diagram
Voronoi-like diagrams
spellingShingle Voronoi diagram
Voronoi-like diagrams
Kolja, Junginger
Evanthia, Papadopoulou
Deletion in Abstract Voronoi Diagrams in Expected Linear Time and Related Problems
description CC BY
format Book
author Kolja, Junginger
Evanthia, Papadopoulou
author_facet Kolja, Junginger
Evanthia, Papadopoulou
author_sort Kolja, Junginger
title Deletion in Abstract Voronoi Diagrams in Expected Linear Time and Related Problems
title_short Deletion in Abstract Voronoi Diagrams in Expected Linear Time and Related Problems
title_full Deletion in Abstract Voronoi Diagrams in Expected Linear Time and Related Problems
title_fullStr Deletion in Abstract Voronoi Diagrams in Expected Linear Time and Related Problems
title_full_unstemmed Deletion in Abstract Voronoi Diagrams in Expected Linear Time and Related Problems
title_sort deletion in abstract voronoi diagrams in expected linear time and related problems
publisher Springer
publishDate 2023
url https://link.springer.com/article/10.1007/s00454-022-00463-z
https://dlib.phenikaa-uni.edu.vn/handle/PNK/7523
_version_ 1762365498652098560
score 8.891145

Similar Items