Searching edges in the overlap of two plane graphs

John Iacono, Elena Khramtcova, Stefan Langerman

Результат исследований: Публикации в книгах, отчётах, сборниках, трудах конференцийстатья в сборнике материалов конференциинаучнаярецензирование


Consider a pair of plane straight-line graphs whose edges are colored red and blue, respectively, and let n be the total complexity of both graphs. We present a O(n log n)-time O(n)-space technique to preprocess such a pair of graphs, that enables efficient searches among the red-blue intersections along edges of one of the graphs. Our technique has a number of applications to geometric problems. This includes: (1) a solution to the batched red-blue search problem [Dehne et al. 2006] in O(n log n) queries to the oracle; (2) an algorithm to compute the maximum vertical distance between a pair of 3D polyhedral terrains, one of which is convex, in O(n log n) time, where n is the total complexity of both terrains; (3) an algorithm to construct the Hausdorff Voronoi diagram of a family of point clusters in the plane in O((n+m) log3n) time and O(n + m) space, where n is the total number of points in all clusters and m is the number of crossings between all clusters; (4) an algorithm to construct the farthest-color Voronoi diagram of the corners of n disjoint axis-aligned rectangles in O(n log2n) time; (5) an algorithm to solve the stabbing circle problem for n parallel line segments in the plane in optimal O(n log n) time. All these results are new or improve on the best known algorithms.

Язык оригиналаанглийский
Название основной публикацииAlgorithms and Data Structures - 15th International Symposium, WADS 2017, Proceedings
РедакторыFaith Ellen, Antonina Kolokolova, Jorg-Rudiger Sack
ИздательSpringer Nature
Число страниц12
ISBN (печатное издание)9783319621265
СостояниеОпубликовано - 1 янв 2017
Событие15th International Symposium on Algorithms and Data Structures, WADS 2017 - St. John’s, Канада
Продолжительность: 31 июл 20172 авг 2017

Серия публикаций

НазваниеLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Том10389 LNCS
ISSN (печатное издание)0302-9743
ISSN (электронное издание)1611-3349


конференция15th International Symposium on Algorithms and Data Structures, WADS 2017
ГородSt. John’s

Предметные области Scopus

  • Теоретические компьютерные науки
  • Компьютерные науки (все)


Подробные сведения о темах исследования «Searching edges in the overlap of two plane graphs». Вместе они формируют уникальный семантический отпечаток (fingerprint).