# The Maximum-Level Vertex in an Arrangement of Lines

Ontology type: schema:ScholarlyArticle      Open Access: True

### Article Info

DATE

2022-01-08

AUTHORS ABSTRACT

Let L be a set of n lines in the plane, not necessarily in general position. We present an efficient algorithm for finding all the vertices of the arrangement A(L)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal{A}(L)$$\end{document} of maximum level, where the level of a vertex v is the number of lines of L that pass strictly below v. The problem, posed in Exercise 8.13 in de Berg et al. (Computational Geometry. Algorithms and Applications. Springer, Berlin (2008)), appears to be much harder than it seems at first sight, as this vertex might not be on the upper envelope of the lines. We first assume that all the lines of L are distinct, and distinguish between two cases, depending on whether or not the upper envelope of L contains a bounded edge. In the former case, we show that the number of lines of L that pass above any maximum level vertex v0\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$v_0$$\end{document} is only O(logn)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(\log n)$$\end{document}. In the latter case, we establish a similar property that holds after we remove some of the lines that are incident to the single vertex of the upper envelope. We present algorithms that run, in both cases, in optimal O(nlogn)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(n\log n)$$\end{document} time. We then consider the case where the lines of L are not necessarily distinct. This setup is more challenging, and for this case we present an algorithm that computes all the maximum-level vertices in time O(n4/3log3n)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(n^{4/3}\log ^{3}\!n)$$\end{document}. Finally, we consider a related combinatorial question for degenerate arrangements, where many lines may intersect in a single point, but all the lines are distinct: We bound the complexity of the weightedk-level in such an arrangement, where the weight of a vertex is the number of lines that pass through the vertex. We show that the bound in this case is O(n4/3)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(n^{4/3})$$\end{document}, which matches the corresponding bound for non-degenerate arrangements, and we use this bound in the analysis of one of our algorithms. More... »

PAGES

439-461

### Journal

TITLE

Discrete & Computational Geometry

ISSUE

2

VOLUME

67

### Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s00454-021-00338-9

DOI

http://dx.doi.org/10.1007/s00454-021-00338-9

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1144501279

Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service:

[
{
"@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json",
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Information and Computing Sciences",
"type": "DefinedTerm"
},
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0801",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Artificial Intelligence and Image Processing",
"type": "DefinedTerm"
}
],
"author": [
{
"affiliation": {
"alternateName": "The Blavatnik School of Computer Science, Tel Aviv University, 69978, Tel Aviv, Israel",
"id": "http://www.grid.ac/institutes/grid.12136.37",
"name": [
"The Blavatnik School of Computer Science, Tel Aviv University, 69978, Tel Aviv, Israel"
],
"type": "Organization"
},
"familyName": "Halperin",
"givenName": "Dan",
"id": "sg:person.011005576423.77",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011005576423.77"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Department of Computer Science, University of Illinois, 201 N. Goodwin Avenue, 61801, Urbana, IL, USA",
"id": "http://www.grid.ac/institutes/grid.35403.31",
"name": [
"Department of Computer Science, University of Illinois, 201 N. Goodwin Avenue, 61801, Urbana, IL, USA"
],
"type": "Organization"
},
"familyName": "Har-Peled",
"givenName": "Sariel",
"id": "sg:person.014322615622.82",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014322615622.82"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Max Planck Institute for Informatics, Saarland Informatics Campus, 66123, Saarbr\u00fccken, Germany",
"id": "http://www.grid.ac/institutes/grid.419528.3",
"name": [
"Max Planck Institute for Informatics, Saarland Informatics Campus, 66123, Saarbr\u00fccken, Germany"
],
"type": "Organization"
},
"familyName": "Mehlhorn",
"givenName": "Kurt",
"id": "sg:person.011757371347.43",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011757371347.43"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Department of Computer Science and Engineering, POSTECH, 37673, Pohang, Korea",
"id": "http://www.grid.ac/institutes/grid.49100.3c",
"name": [
"Department of Computer Science and Engineering, POSTECH, 37673, Pohang, Korea"
],
"type": "Organization"
},
"familyName": "Oh",
"givenName": "Eunjin",
"id": "sg:person.010624474131.36",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010624474131.36"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "The Blavatnik School of Computer Science, Tel Aviv University, 69978, Tel Aviv, Israel",
"id": "http://www.grid.ac/institutes/grid.12136.37",
"name": [
"The Blavatnik School of Computer Science, Tel Aviv University, 69978, Tel Aviv, Israel"
],
"type": "Organization"
},
"familyName": "Sharir",
"givenName": "Micha",
"id": "sg:person.013672552025.49",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013672552025.49"
],
"type": "Person"
}
],
"citation": [
{
"id": "sg:pub.10.1007/pl00009354",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1027985175",
"https://doi.org/10.1007/pl00009354"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bf02187740",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1041585569",
"https://doi.org/10.1007/bf02187740"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-540-77974-2",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1045724697",
"https://doi.org/10.1007/978-3-540-77974-2"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/s00453-002-0999-9",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1043637888",
"https://doi.org/10.1007/s00453-002-0999-9"
],
"type": "CreativeWork"
}
],
"datePublished": "2022-01-08",
"datePublishedReg": "2022-01-08",
"description": "Let L be a set of n lines in the plane, not necessarily in general position. We present an efficient algorithm for finding all the vertices of the arrangement A(L)\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$\\mathcal{A}(L)$$\\end{document} of maximum level, where the level of a vertex v is the number of lines of L that pass strictly below\u00a0v. The problem, posed in Exercise\u00a08.13 in de Berg et al. (Computational Geometry. Algorithms and Applications. Springer, Berlin (2008)), appears to be much harder than it seems at first sight, as this vertex might not be on the upper envelope of the lines. We first assume that all the lines of L are distinct, and distinguish between two cases, depending on whether or not the upper envelope of L contains a bounded edge. In the former case, we show that the number of lines of L that pass above any maximum level vertex v0\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$v_0$$\\end{document} is only O(logn)\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$O(\\log n)$$\\end{document}. In the latter case, we establish a similar property that holds after we remove some of the lines that are incident to the single vertex of the upper envelope. We present algorithms that run, in both cases, in optimal O(nlogn)\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$O(n\\log n)$$\\end{document} time. We then consider the case where the lines of L are not necessarily distinct. This setup is more challenging, and for this case we present an algorithm that computes all the maximum-level vertices in time O(n4/3log3n)\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$O(n^{4/3}\\log ^{3}\\!n)$$\\end{document}. Finally, we consider a related combinatorial question for degenerate arrangements, where many lines may intersect in a single point, but all the lines are distinct: We bound the complexity of the weightedk-level in such an arrangement, where the weight of a vertex is the number of lines that pass through the vertex. We show that the bound in this case is O(n4/3)\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$O(n^{4/3})$$\\end{document}, which matches the corresponding bound for non-degenerate arrangements, and we use this bound in the analysis of one of our algorithms.",
"genre": "article",
"id": "sg:pub.10.1007/s00454-021-00338-9",
"isAccessibleForFree": true,
"isFundedItemOf": [
{
"id": "sg:grant.9645143",
"type": "MonetaryGrant"
},
{
"id": "sg:grant.8523088",
"type": "MonetaryGrant"
}
],
"isPartOf": [
{
"id": "sg:journal.1043660",
"issn": [
"0179-5376",
"1432-0444"
],
"name": "Discrete & Computational Geometry",
"publisher": "Springer Nature",
"type": "Periodical"
},
{
"issueNumber": "2",
"type": "PublicationIssue"
},
{
"type": "PublicationVolume",
}
],
"keywords": [
"efficient algorithm",
"algorithm",
"number of lines",
"single point",
"vertices",
"single vertex",
"upper envelope",
"combinatorial questions",
"complexity",
"set",
"arrangement of lines",
"number",
"time",
"setup",
"vertex v",
"edge",
"n lines",
"et al",
"first sight",
"sight",
"point",
"general position",
"cases",
"similar properties",
"lines",
"position",
"former case",
"latter case",
"questions",
"analysis",
"plane",
"arrangement",
"levels",
"Berg et al",
"envelope",
"weight",
"problem",
"al",
"properties",
"exercise",
"maximum level"
],
"name": "The Maximum-Level Vertex in an Arrangement of Lines",
"pagination": "439-461",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1144501279"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/s00454-021-00338-9"
]
}
],
"sameAs": [
"https://doi.org/10.1007/s00454-021-00338-9",
"https://app.dimensions.ai/details/publication/pub.1144501279"
],
"sdDataset": "articles",
"sdDatePublished": "2022-10-01T06:49",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-springernature-scigraph/baseset/20221001/entities/gbq_results/article/article_935.jsonl",
"type": "ScholarlyArticle",
"url": "https://doi.org/10.1007/s00454-021-00338-9"
}
]

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/s00454-021-00338-9'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/s00454-021-00338-9'

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00454-021-00338-9'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00454-021-00338-9'

This table displays all metadata directly associated to this object as RDF triples.

155 TRIPLES      21 PREDICATES      69 URIs      57 LITERALS      6 BLANK NODES

Subject Predicate Object
2 anzsrc-for:0801
3 schema:author Nb15306b1fb2b4b64881148c675af17bd
4 schema:citation sg:pub.10.1007/978-3-540-77974-2
5 sg:pub.10.1007/bf02187740
6 sg:pub.10.1007/pl00009354
7 sg:pub.10.1007/s00453-002-0999-9
8 schema:datePublished 2022-01-08
9 schema:datePublishedReg 2022-01-08
10 schema:description Let L be a set of n lines in the plane, not necessarily in general position. We present an efficient algorithm for finding all the vertices of the arrangement A(L)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal{A}(L)$$\end{document} of maximum level, where the level of a vertex v is the number of lines of L that pass strictly below v. The problem, posed in Exercise 8.13 in de Berg et al. (Computational Geometry. Algorithms and Applications. Springer, Berlin (2008)), appears to be much harder than it seems at first sight, as this vertex might not be on the upper envelope of the lines. We first assume that all the lines of L are distinct, and distinguish between two cases, depending on whether or not the upper envelope of L contains a bounded edge. In the former case, we show that the number of lines of L that pass above any maximum level vertex v0\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$v_0$$\end{document} is only O(logn)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(\log n)$$\end{document}. In the latter case, we establish a similar property that holds after we remove some of the lines that are incident to the single vertex of the upper envelope. We present algorithms that run, in both cases, in optimal O(nlogn)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(n\log n)$$\end{document} time. We then consider the case where the lines of L are not necessarily distinct. This setup is more challenging, and for this case we present an algorithm that computes all the maximum-level vertices in time O(n4/3log3n)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(n^{4/3}\log ^{3}\!n)$$\end{document}. Finally, we consider a related combinatorial question for degenerate arrangements, where many lines may intersect in a single point, but all the lines are distinct: We bound the complexity of the weightedk-level in such an arrangement, where the weight of a vertex is the number of lines that pass through the vertex. We show that the bound in this case is O(n4/3)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(n^{4/3})$$\end{document}, which matches the corresponding bound for non-degenerate arrangements, and we use this bound in the analysis of one of our algorithms.
11 schema:genre article
12 schema:isAccessibleForFree true
13 schema:isPartOf Na6ab3dd9cea2454da81db791cb48b08c
15 sg:journal.1043660
16 schema:keywords Berg et al
17 al
18 algorithm
19 analysis
20 arrangement
21 arrangement of lines
22 cases
23 combinatorial questions
24 complexity
25 edge
26 efficient algorithm
27 envelope
28 et al
29 exercise
30 first sight
31 former case
32 general position
33 latter case
34 levels
35 lines
36 maximum level
37 n lines
38 number
39 number of lines
40 plane
41 point
42 position
43 problem
44 properties
45 questions
46 set
47 setup
48 sight
49 similar properties
50 single point
51 single vertex
52 time
53 upper envelope
54 vertex v
55 vertices
56 weight
57 schema:name The Maximum-Level Vertex in an Arrangement of Lines
58 schema:pagination 439-461
59 schema:productId N90a198d843b3413f9025f214940e28ff
60 N916e5900cbd1427bae98dd04ea9b0216
61 schema:sameAs https://app.dimensions.ai/details/publication/pub.1144501279
62 https://doi.org/10.1007/s00454-021-00338-9
63 schema:sdDatePublished 2022-10-01T06:49
65 schema:sdPublisher N61ddc66d1e3a4b74852b568667853b78
66 schema:url https://doi.org/10.1007/s00454-021-00338-9
68 sgo:sdDataset articles
69 rdf:type schema:ScholarlyArticle
71 rdf:rest N1b96403d8f344d789fc1c84fe30eaab2
72 N1178ec3e91434078829cba93e97bce0d rdf:first sg:person.014322615622.82
73 rdf:rest Nb4176f943f694c9e8f06abddab2930a1
74 N1b96403d8f344d789fc1c84fe30eaab2 rdf:first sg:person.013672552025.49
75 rdf:rest rdf:nil
76 N61ddc66d1e3a4b74852b568667853b78 schema:name Springer Nature - SN SciGraph project
77 rdf:type schema:Organization
78 N90a198d843b3413f9025f214940e28ff schema:name doi
79 schema:value 10.1007/s00454-021-00338-9
80 rdf:type schema:PropertyValue
81 N916e5900cbd1427bae98dd04ea9b0216 schema:name dimensions_id
82 schema:value pub.1144501279
83 rdf:type schema:PropertyValue
85 rdf:type schema:PublicationVolume
86 Nb15306b1fb2b4b64881148c675af17bd rdf:first sg:person.011005576423.77
87 rdf:rest N1178ec3e91434078829cba93e97bce0d
88 Nb4176f943f694c9e8f06abddab2930a1 rdf:first sg:person.011757371347.43
91 rdf:type schema:PublicationIssue
92 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
93 schema:name Information and Computing Sciences
94 rdf:type schema:DefinedTerm
95 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
96 schema:name Artificial Intelligence and Image Processing
97 rdf:type schema:DefinedTerm
98 sg:grant.8523088 http://pending.schema.org/fundedItem sg:pub.10.1007/s00454-021-00338-9
99 rdf:type schema:MonetaryGrant
100 sg:grant.9645143 http://pending.schema.org/fundedItem sg:pub.10.1007/s00454-021-00338-9
101 rdf:type schema:MonetaryGrant
102 sg:journal.1043660 schema:issn 0179-5376
103 1432-0444
104 schema:name Discrete & Computational Geometry
105 schema:publisher Springer Nature
106 rdf:type schema:Periodical
107 sg:person.010624474131.36 schema:affiliation grid-institutes:grid.49100.3c
108 schema:familyName Oh
109 schema:givenName Eunjin
110 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010624474131.36
111 rdf:type schema:Person
112 sg:person.011005576423.77 schema:affiliation grid-institutes:grid.12136.37
113 schema:familyName Halperin
114 schema:givenName Dan
115 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011005576423.77
116 rdf:type schema:Person
117 sg:person.011757371347.43 schema:affiliation grid-institutes:grid.419528.3
118 schema:familyName Mehlhorn
119 schema:givenName Kurt
120 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011757371347.43
121 rdf:type schema:Person
122 sg:person.013672552025.49 schema:affiliation grid-institutes:grid.12136.37
123 schema:familyName Sharir
124 schema:givenName Micha
125 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013672552025.49
126 rdf:type schema:Person
127 sg:person.014322615622.82 schema:affiliation grid-institutes:grid.35403.31
128 schema:familyName Har-Peled
129 schema:givenName Sariel
130 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014322615622.82
131 rdf:type schema:Person
132 sg:pub.10.1007/978-3-540-77974-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045724697
133 https://doi.org/10.1007/978-3-540-77974-2
134 rdf:type schema:CreativeWork
135 sg:pub.10.1007/bf02187740 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041585569
136 https://doi.org/10.1007/bf02187740
137 rdf:type schema:CreativeWork
138 sg:pub.10.1007/pl00009354 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027985175
139 https://doi.org/10.1007/pl00009354
140 rdf:type schema:CreativeWork
141 sg:pub.10.1007/s00453-002-0999-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043637888
142 https://doi.org/10.1007/s00453-002-0999-9
143 rdf:type schema:CreativeWork
144 grid-institutes:grid.12136.37 schema:alternateName The Blavatnik School of Computer Science, Tel Aviv University, 69978, Tel Aviv, Israel
145 schema:name The Blavatnik School of Computer Science, Tel Aviv University, 69978, Tel Aviv, Israel
146 rdf:type schema:Organization
147 grid-institutes:grid.35403.31 schema:alternateName Department of Computer Science, University of Illinois, 201 N. Goodwin Avenue, 61801, Urbana, IL, USA
148 schema:name Department of Computer Science, University of Illinois, 201 N. Goodwin Avenue, 61801, Urbana, IL, USA
149 rdf:type schema:Organization
150 grid-institutes:grid.419528.3 schema:alternateName Max Planck Institute for Informatics, Saarland Informatics Campus, 66123, Saarbrücken, Germany
151 schema:name Max Planck Institute for Informatics, Saarland Informatics Campus, 66123, Saarbrücken, Germany
152 rdf:type schema:Organization
153 grid-institutes:grid.49100.3c schema:alternateName Department of Computer Science and Engineering, POSTECH, 37673, Pohang, Korea
154 schema:name Department of Computer Science and Engineering, POSTECH, 37673, Pohang, Korea
155 rdf:type schema:Organization