Euclidean minimum spanning tree: Difference between revisions

Revision as of 21:00, 12 September 2022

Revision as of 01:36, 25 September 2022

Line 134:

| title = Algorithms and Data Structures: 17th International Symposium, WADS 2021, Virtual Event, August 9–11, 2021, Proceedings

| volume = 12808

| year = 2021}}</ref>| s2cid = 234599877

| year = 1998}}</ref>

<ref name=abcfks>{{citation

Line 162 ⟶ 163:

| publisher = IEEE Computer Society

| title = 39th Annual Symposium on Foundations of Computer Science, FOCS '98, November 8–11, 1998, Palo Alto, California, USA

| year = 1998| s2cid = 2559456 | url = https://infoscience.epfl.ch/record/99344/files/AgarwalEGH98.pdf }}</ref>

| year = 1998}}</ref>

<ref name=aesw>{{citation

Line 214 ⟶ 215:

| pages = 698–706

| title = 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26-29 October, 2013, Berkeley, CA, USA

| year = 2013}}</ref>| s2cid = 17514182

| year = 1980}}</ref>

<ref name=bdek>{{citation

Line 253 ⟶ 255:

| publisher = Association for Computing Machinery

| title = Proceedings of the Thirteenth Annual Symposium on Computational Geometry, Nice, France, June 4–6, 1997

| year = 1997}}</ref>| s2cid = 15556637

| year = 1989}}</ref>

<ref name=bm09>{{citation

Line 265 ⟶ 268:

| title = Delaunay triangulations in {{mvar|O}}(sort({{mvar|n}})) time and more

| volume = 58

| year = 2011}}</ref>| s2cid = 11316974

}}</ref>

<ref name=bwy>{{citation

Line 278 ⟶ 282:

| title = Optimal expected-time algorithms for closest point problems

| volume = 6

| year = 1980| s2cid = 17238717 | url = https://figshare.com/articles/journal_contribution/Optimal_expected-time_algorithms_for_closest-point_problems/6608108 }}</ref>

| year = 1980}}</ref>

<ref name=cck>{{citation

Line 303 ⟶ 307:

| title = A dynamic data structure for 3-D convex hulls and 2-D nearest neighbor queries

| volume = 57

| year = 2010| s2cid = 47454142 }}</ref>

<ref name=chalev>{{citation

Line 314 ⟶ 318:

| title = On levels in arrangements of curves

| volume = 29

| year = 2003| s2cid = 18966889 }}</ref>

<ref name=chrvp>{{citation

Line 327 ⟶ 331:

| publisher = IEEE Computer Society

| title = 17th International Parallel and Distributed Processing Symposium (IPDPS 2003), 22-26 April 2003, Nice, France, Proceedings

| year = 2003}}</ref>| s2cid = 17863487

}}</ref>

<ref name=clarkson>{{citation

| last = Clarkson | first = Kenneth L. | author-link = Kenneth L. Clarkson

| doi = 10.1007/BF01553902

| issue = 1-4

| journal = [[Algorithmica]]

| mr = 1019387

Line 338 ⟶ 343:

| title = An algorithm for geometric minimum spanning trees requiring nearly linear expected time

| volume = 4

| year = 1989| s2cid = 22176641 }}</ref>

<ref name=comment>{{citation

Line 348 ⟶ 353:

| title = Comment: Algorithms for computing relative neighborhood graph

| volume = 16

| year = 1980| bibcode = 1980ElL....16..860T }}; reply by Urquhart, [[doi:10.1049/el:19800612|pp. 860–861]]</ref>

<ref name=devillers>{{citation

Line 360 ⟶ 365:

| url = https://hal.inria.fr/inria-00167206/file/hal.pdf

| volume = 2

| year = 1992}}</ref>| s2cid = 60203

}}</ref>

<ref name=dwyer>{{citation

Line 406 ⟶ 412:

| title = Dynamic Euclidean minimum spanning trees and extrema of binary functions

| volume = 13

| year = 1995| s2cid = 7339165 }}</ref>

<ref name=fknp>{{citation

Line 420 ⟶ 426:

| title = Improved approximation results for the minimum energy broadcasting problem

| volume = 49

| year = 2007}}</ref>| s2cid = 11982404

}}</ref>

<ref name=frakau>{{citation

Line 432 ⟶ 439:

| title = Polynomial area bounds for MST embeddings of trees

| volume = 44

| year = 2011}}</ref>| s2cid = 5634139

}}</ref>

<ref name=gilpol>{{citation

Line 444 ⟶ 452:

| title = Steiner minimal trees

| volume = 16

| year = 1968| issue = 1 }}</ref>

<ref name=gowros>{{citation

Line 456 ⟶ 464:

| title = Minimum spanning trees and single linkage cluster analysis

| volume = 18

| year = 1969| issue = 1
}}</ref>

<ref name=history>{{citation

Line 468 ⟶ 477:

| title = On the history of the minimum spanning tree problem

| volume = 7

| year = 1985| s2cid = 10555375 }}</ref>

<ref name=king>{{citation

Line 491 ⟶ 500:

| title = A randomized linear-time algorithm to find minimum spanning trees

| volume = 42

| year = 1995| s2cid = 832583 }}</ref>

<ref name=kln>{{citation

Line 538 ⟶ 547:

| pages = 428–437

| title = Formal procedures for connecting terminals with a minimum total wire length

| volume = 4}}</ref>| s2cid = 7320964

}}</ref>

<ref name=mares>{{citation

Line 561 ⟶ 571:

| title = Transitions in geometric minimum spanning trees

| volume = 8

| year = 1992}}</ref>| s2cid = 30101649

}}</ref>

<ref name=mrg>{{citation

Line 575 ⟶ 586:

| pages = 603–612

| title = Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Washington, DC, USA, July 25-28, 2010

| year = 2010}}</ref>| s2cid = 186025

}}</ref>

<ref name=msvw>{{citation

Line 592 ⟶ 604:

| title = LATIN 2018: Theoretical Informatics – 13th Latin American Symposium, Buenos Aires, Argentina, April 16–19, 2018, Proceedings

| volume = 10807

| year = 2018}}</ref>| s2cid = 4709616

| url = https://research.tue.nl/nl/publications/bde45eae-314a-42b4-8dca-9a0a420f38e1

}}</ref>

<ref name=nzz>{{citation

Line 635 ⟶ 649:

| series = Texts and Monographs in Computer Science

| title = Computational Geometry: An Introduction

| year = 1985| s2cid = 206656565 }}</ref>

<ref name=rakwz>{{citation

Line 650 ⟶ 664:

| title = A simple, faster method for kinetic proximity problems

| volume = 48

| year = 2015}}</ref>| s2cid = 18971251

}}</ref>

<ref name=robsal>{{citation

Line 662 ⟶ 677:

| title = Low-degree minimum spanning trees

| volume = 14

| year = 1995}}</ref>| s2cid = 16040977

}}</ref>

<ref name=rzcomb>{{citation

Line 694 ⟶ 710:

| title = 16th Annual Symposium on Foundations of Computer Science, Berkeley, California, USA, October 13-15, 1975

| title-link = Symposium on Foundations of Computer Science

| year = 1975| s2cid = 40615455 }}</ref>

<ref name=ss89>{{citation

Line 706 ⟶ 722:

| title = Worst-case growth rates of some classical problems of combinatorial optimization

| volume = 18

| year = 1989| url = https://repository.upenn.edu/cgi/viewcontent.cgi?article=1048&context=oid_papers }}</ref>

| year = 1989}}</ref>

<ref name=sse>{{citation

Line 719 ⟶ 735:

| title = On the number of leaves of a Euclidean minimal spanning tree

| volume = 24

| year = 1987| jstor = 3214207 | s2cid = 29026025 }}</ref>

<ref name=steele>{{citation

Line 749 ⟶ 765:

| pages = 450–475

| title = An extended minimum spanning tree method for characterizing local urban patterns

| volume = 32}}</ref>| s2cid = 46772272

}}</ref>

<ref name=wclf>{{citation

Line 762 ⟶ 779:

| title = Minimum-energy broadcasting in static ad hoc wireless networks

| volume = 8

| year = 2002}}</ref>| s2cid = 1297518

}}</ref>

<ref name=yao82>{{citation