On Fully Diverse Sets of Geometric Objects and Graphs

Fabian Klute; Marc van Kreveld

doi:10.1007/978-3-031-15914-5_24

On Fully Diverse Sets of Geometric Objects and Graphs

Fabian Klute
, Marc van Kreveld

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

Abstract

Diversity is a property of sets that shows how varied or different its elements are. We define full diversity in a metric space and study the maximum size of fully diverse sets. A set is fully diverse if each pair of elements is as distant as the maximum possible distance between any pair, up to a constant factor. We study metric spaces based on geometry, embeddings of graphs, and graphs themselves. In the geometric cases, we study measures like Hausdorff distance, Frechét distance, and area of symmetric difference between objects in a bounded region. In the embedding cases, we study planar embeddings of trees and planar graphs, and use the number of swaps in the rotation system as the metric. In the graph cases, we use the number of insertions and deletions of leaves or edges as the metric. In most cases, we show (almost) tight lower and upper bounds on the maximum size of fully diverse sets. Our results lead to a very simple randomized algorithm to generate large fully diverse sets in several cases.

Original language	English
Title of host publication	Graph-Theoretic Concepts in Computer Science
Subtitle of host publication	48th International Workshop, WG 2022, Tübingen, Germany, June 22–24, 2022, Revised Selected Papers
Editors	Michael A. Bekos, Michael Kaufmann
Place of Publication	Cham
Publisher	Springer
Pages	328-341
Number of pages	14
Edition	1
ISBN (Electronic)	978-3-031-15914-5
ISBN (Print)	978-3-031-15913-8
DOIs	https://doi.org/10.1007/978-3-031-15914-5_24
Publication status	Published - 1 Oct 2022

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	13453
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Bibliographical note

Funding Information:
Supported by the Netherlands Organisation for Scientific Research (NWO) under project no. 612.001.651 and the Austrian Science Foundation (FWF) grant J4510.

Publisher Copyright:
© 2022, Springer Nature Switzerland AG.

Keywords

Distance Measures
Diverse Embeddings
Diverse Geometric Objects
Diverse Graphs
Diversity

Access to Document

10.1007/978-3-031-15914-5_24

978-3-031-15914-5_24Final published version, 375 KBLicence: Taverne

Cite this

Klute, F., & Kreveld, M. V. (2022). On Fully Diverse Sets of Geometric Objects and Graphs. In M. A. Bekos, & M. Kaufmann (Eds.), Graph-Theoretic Concepts in Computer Science: 48th International Workshop, WG 2022, Tübingen, Germany, June 22–24, 2022, Revised Selected Papers (1 ed., pp. 328-341). (Lecture Notes in Computer Science ; Vol. 13453 ). Springer. https://doi.org/10.1007/978-3-031-15914-5_24

@inproceedings{8bf22be088824842b62d0e437a7e1253,

title = "On Fully Diverse Sets of Geometric Objects and Graphs",

abstract = "Diversity is a property of sets that shows how varied or different its elements are. We define full diversity in a metric space and study the maximum size of fully diverse sets. A set is fully diverse if each pair of elements is as distant as the maximum possible distance between any pair, up to a constant factor. We study metric spaces based on geometry, embeddings of graphs, and graphs themselves. In the geometric cases, we study measures like Hausdorff distance, Frech{\'e}t distance, and area of symmetric difference between objects in a bounded region. In the embedding cases, we study planar embeddings of trees and planar graphs, and use the number of swaps in the rotation system as the metric. In the graph cases, we use the number of insertions and deletions of leaves or edges as the metric. In most cases, we show (almost) tight lower and upper bounds on the maximum size of fully diverse sets. Our results lead to a very simple randomized algorithm to generate large fully diverse sets in several cases.",

keywords = "Distance Measures, Diverse Embeddings, Diverse Geometric Objects, Diverse Graphs, Diversity",

author = "Fabian Klute and Kreveld, \{Marc van\}",

note = "Funding Information: Supported by the Netherlands Organisation for Scientific Research (NWO) under project no. 612.001.651 and the Austrian Science Foundation (FWF) grant J4510. Publisher Copyright: {\textcopyright} 2022, Springer Nature Switzerland AG.",

year = "2022",

month = oct,

day = "1",

doi = "10.1007/978-3-031-15914-5\_24",

language = "English",

isbn = "978-3-031-15913-8",

series = "Lecture Notes in Computer Science ",

publisher = "Springer",

pages = "328--341",

editor = "Bekos, \{Michael A.\} and Michael Kaufmann",

booktitle = "Graph-Theoretic Concepts in Computer Science",

edition = "1",

}

Klute, F & Kreveld, MV 2022, On Fully Diverse Sets of Geometric Objects and Graphs. in MA Bekos & M Kaufmann (eds), Graph-Theoretic Concepts in Computer Science: 48th International Workshop, WG 2022, Tübingen, Germany, June 22–24, 2022, Revised Selected Papers. 1 edn, Lecture Notes in Computer Science , vol. 13453 , Springer, Cham, pp. 328-341. https://doi.org/10.1007/978-3-031-15914-5_24

On Fully Diverse Sets of Geometric Objects and Graphs. / Klute, Fabian; Kreveld, Marc van.
Graph-Theoretic Concepts in Computer Science: 48th International Workshop, WG 2022, Tübingen, Germany, June 22–24, 2022, Revised Selected Papers. ed. / Michael A. Bekos; Michael Kaufmann. 1. ed. Cham: Springer, 2022. p. 328-341 (Lecture Notes in Computer Science ; Vol. 13453 ).

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

TY - GEN

T1 - On Fully Diverse Sets of Geometric Objects and Graphs

AU - Klute, Fabian

AU - Kreveld, Marc van

N1 - Funding Information: Supported by the Netherlands Organisation for Scientific Research (NWO) under project no. 612.001.651 and the Austrian Science Foundation (FWF) grant J4510. Publisher Copyright: © 2022, Springer Nature Switzerland AG.

PY - 2022/10/1

Y1 - 2022/10/1

N2 - Diversity is a property of sets that shows how varied or different its elements are. We define full diversity in a metric space and study the maximum size of fully diverse sets. A set is fully diverse if each pair of elements is as distant as the maximum possible distance between any pair, up to a constant factor. We study metric spaces based on geometry, embeddings of graphs, and graphs themselves. In the geometric cases, we study measures like Hausdorff distance, Frechét distance, and area of symmetric difference between objects in a bounded region. In the embedding cases, we study planar embeddings of trees and planar graphs, and use the number of swaps in the rotation system as the metric. In the graph cases, we use the number of insertions and deletions of leaves or edges as the metric. In most cases, we show (almost) tight lower and upper bounds on the maximum size of fully diverse sets. Our results lead to a very simple randomized algorithm to generate large fully diverse sets in several cases.

AB - Diversity is a property of sets that shows how varied or different its elements are. We define full diversity in a metric space and study the maximum size of fully diverse sets. A set is fully diverse if each pair of elements is as distant as the maximum possible distance between any pair, up to a constant factor. We study metric spaces based on geometry, embeddings of graphs, and graphs themselves. In the geometric cases, we study measures like Hausdorff distance, Frechét distance, and area of symmetric difference between objects in a bounded region. In the embedding cases, we study planar embeddings of trees and planar graphs, and use the number of swaps in the rotation system as the metric. In the graph cases, we use the number of insertions and deletions of leaves or edges as the metric. In most cases, we show (almost) tight lower and upper bounds on the maximum size of fully diverse sets. Our results lead to a very simple randomized algorithm to generate large fully diverse sets in several cases.

KW - Distance Measures

KW - Diverse Embeddings

KW - Diverse Geometric Objects

KW - Diverse Graphs

KW - Diversity

UR - https://www.scopus.com/pages/publications/85140740650

U2 - 10.1007/978-3-031-15914-5_24

DO - 10.1007/978-3-031-15914-5_24

M3 - Conference contribution

SN - 978-3-031-15913-8

T3 - Lecture Notes in Computer Science

SP - 328

EP - 341

BT - Graph-Theoretic Concepts in Computer Science

A2 - Bekos, Michael A.

A2 - Kaufmann, Michael

PB - Springer

CY - Cham

ER -

Klute F, Kreveld MV. On Fully Diverse Sets of Geometric Objects and Graphs. In Bekos MA, Kaufmann M, editors, Graph-Theoretic Concepts in Computer Science: 48th International Workshop, WG 2022, Tübingen, Germany, June 22–24, 2022, Revised Selected Papers. 1 ed. Cham: Springer. 2022. p. 328-341. (Lecture Notes in Computer Science ). doi: 10.1007/978-3-031-15914-5_24