Standard

Randomized incremental construction for the hausdorff voronoi diagram revisited and extended. / Khramtcova, Elena; Papadopoulou, Evanthia.

Computing and Combinatorics - 23rd International Conference, COCOON 2017, Proceedings. ed. / Yixin Cao; Jianer Chen. Springer Nature, 2017. p. 321-332 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10392 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review

Harvard

Khramtcova, E & Papadopoulou, E 2017, Randomized incremental construction for the hausdorff voronoi diagram revisited and extended. in Y Cao & J Chen (eds), Computing and Combinatorics - 23rd International Conference, COCOON 2017, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10392 LNCS, Springer Nature, pp. 321-332, 23rd International Conference on Computing and Combinatorics, COCOON 2017, Hong Kong, China, 3/08/17. https://doi.org/10.1007/978-3-319-62389-4_27

APA

Khramtcova, E., & Papadopoulou, E. (2017). Randomized incremental construction for the hausdorff voronoi diagram revisited and extended. In Y. Cao, & J. Chen (Eds.), Computing and Combinatorics - 23rd International Conference, COCOON 2017, Proceedings (pp. 321-332). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10392 LNCS). Springer Nature. https://doi.org/10.1007/978-3-319-62389-4_27

Vancouver

Khramtcova E, Papadopoulou E. Randomized incremental construction for the hausdorff voronoi diagram revisited and extended. In Cao Y, Chen J, editors, Computing and Combinatorics - 23rd International Conference, COCOON 2017, Proceedings. Springer Nature. 2017. p. 321-332. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-319-62389-4_27

Author

Khramtcova, Elena ; Papadopoulou, Evanthia. / Randomized incremental construction for the hausdorff voronoi diagram revisited and extended. Computing and Combinatorics - 23rd International Conference, COCOON 2017, Proceedings. editor / Yixin Cao ; Jianer Chen. Springer Nature, 2017. pp. 321-332 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inproceedings{2c51a2beb99f40a7a18d2d9e28eeb9fb,
title = "Randomized incremental construction for the hausdorff voronoi diagram revisited and extended",
abstract = "The Hausdorff Voronoi diagram of clusters of points in the plane is a generalization of Voronoi diagrams based on the Hausdorff distance function. Its combinatorial complexity is O(n+m), where n is the total number of points and m is the number of crossings between the input clusters (formula presented) the number of clusters is k. We present efficient algorithms to construct this diagram via the randomized incremental construction (RIC) framework For non-crossing clusters (m=0), our algorithm runs in expected (formula presented) time and deterministic O(n) space. For arbitrary clusters the algorithm runs in expected (formula presented) space. The two algorithms can be combined in a crossing-oblivious scheme within the same bounds. We show how to apply the RIC framework efficiently to handle non-standard characteristics of generalized Voronoi diagrams, including sites (and bisectors) of non-constant complexity, sites that are not enclosed in their Voronoi regions, empty Voronoi regions, and finally, disconnected bisectors and Voronoi regions. The diagram finds direct applications.",
author = "Elena Khramtcova and Evanthia Papadopoulou",
year = "2017",
month = jan,
day = "1",
doi = "10.1007/978-3-319-62389-4_27",
language = "English",
isbn = "9783319623887",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Nature",
pages = "321--332",
editor = "Yixin Cao and Jianer Chen",
booktitle = "Computing and Combinatorics - 23rd International Conference, COCOON 2017, Proceedings",
address = "Germany",
note = "23rd International Conference on Computing and Combinatorics, COCOON 2017 ; Conference date: 03-08-2017 Through 05-08-2017",

}

RIS

TY - GEN

T1 - Randomized incremental construction for the hausdorff voronoi diagram revisited and extended

AU - Khramtcova, Elena

AU - Papadopoulou, Evanthia

PY - 2017/1/1

Y1 - 2017/1/1

N2 - The Hausdorff Voronoi diagram of clusters of points in the plane is a generalization of Voronoi diagrams based on the Hausdorff distance function. Its combinatorial complexity is O(n+m), where n is the total number of points and m is the number of crossings between the input clusters (formula presented) the number of clusters is k. We present efficient algorithms to construct this diagram via the randomized incremental construction (RIC) framework For non-crossing clusters (m=0), our algorithm runs in expected (formula presented) time and deterministic O(n) space. For arbitrary clusters the algorithm runs in expected (formula presented) space. The two algorithms can be combined in a crossing-oblivious scheme within the same bounds. We show how to apply the RIC framework efficiently to handle non-standard characteristics of generalized Voronoi diagrams, including sites (and bisectors) of non-constant complexity, sites that are not enclosed in their Voronoi regions, empty Voronoi regions, and finally, disconnected bisectors and Voronoi regions. The diagram finds direct applications.

AB - The Hausdorff Voronoi diagram of clusters of points in the plane is a generalization of Voronoi diagrams based on the Hausdorff distance function. Its combinatorial complexity is O(n+m), where n is the total number of points and m is the number of crossings between the input clusters (formula presented) the number of clusters is k. We present efficient algorithms to construct this diagram via the randomized incremental construction (RIC) framework For non-crossing clusters (m=0), our algorithm runs in expected (formula presented) time and deterministic O(n) space. For arbitrary clusters the algorithm runs in expected (formula presented) space. The two algorithms can be combined in a crossing-oblivious scheme within the same bounds. We show how to apply the RIC framework efficiently to handle non-standard characteristics of generalized Voronoi diagrams, including sites (and bisectors) of non-constant complexity, sites that are not enclosed in their Voronoi regions, empty Voronoi regions, and finally, disconnected bisectors and Voronoi regions. The diagram finds direct applications.

UR - http://www.scopus.com/inward/record.url?scp=85028460819&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-62389-4_27

DO - 10.1007/978-3-319-62389-4_27

M3 - Conference contribution

AN - SCOPUS:85028460819

SN - 9783319623887

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 321

EP - 332

BT - Computing and Combinatorics - 23rd International Conference, COCOON 2017, Proceedings

A2 - Cao, Yixin

A2 - Chen, Jianer

PB - Springer Nature

T2 - 23rd International Conference on Computing and Combinatorics, COCOON 2017

Y2 - 3 August 2017 through 5 August 2017

ER -

ID: 38614848