Deletion in Abstract Voronoi Diagrams in Expected Linear Time and Related Problems
CC BY
Lưu vào:
| Tác giả chính: | , |
|---|---|
| Định dạng: | Sách |
| Ngôn ngữ: | English |
| Nhà xuất bản: |
Springer
2023
|
| Chủ đề: | |
| Truy cập trực tuyến: | https://link.springer.com/article/10.1007/s00454-022-00463-z https://dlib.phenikaa-uni.edu.vn/handle/PNK/7523 |
| Từ khóa: |
Thêm từ khóa
Không có từ khóa, Hãy là người đầu tiên đánh dấu biểu ghi này!
|
| 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.893527 |