About: Farthest-first traversal

Facets (new session)
Description
Metadata
Settings
- Rule:
- Inverse Functional Properties:
- "Same As":

About: Farthest-first traversal Goto Sponge NotDistinct Permalink

An Entity of Type : owl:Thing, within Data Space : el.dbpedia.org associated with source document(s)

In computational geometry, the farthest-first traversal of a compact metric space is a sequence of points in the space, where the first point is selected arbitrarily and each successive point is as far as possible from the set of previously-selected points. The same concept can also be applied to a finite set of geometric points, by restricting the selected points to belong to the set or equivalently by considering the finite metric space generated by these points. For a finite metric space or finite set of geometric points, the resulting sequence forms a permutation of the points, also known as the greedy permutation.

Attributes	Values
rdfs:label	Farthest-first traversal (en)
rdfs:comment	In computational geometry, the farthest-first traversal of a compact metric space is a sequence of points in the space, where the first point is selected arbitrarily and each successive point is as far as possible from the set of previously-selected points. The same concept can also be applied to a finite set of geometric points, by restricting the selected points to belong to the set or equivalently by considering the finite metric space generated by these points. For a finite metric space or finite set of geometric points, the resulting sequence forms a permutation of the points, also known as the greedy permutation. (en)
sameAs	Farthest-first traversal
dbp:wikiPageUsesTemplate	dbt:Good_article dbt:Harvtxt dbt:Math dbt:Mvar dbt:R dbt:Reflist dbt:Short_description
Subject	Approximation algorithms Cluster analysis Computational geometry
thumbnail	wiki-commons:Special:FilePath/Farthest-first_traversal.svg?width=300
foaf:depiction
gold:hypernym	Sequence
prov:wasDerivedFrom	http://en.wikipedia.org/wiki/Farthest-first_traversal?oldid=1067776967&ns=0
Wikipage page ID	47226218 (xsd:integer)
page length (characters) of wiki page	27838 (xsd:nonNegativeInteger)
Wikipage revision ID	1067776967 (xsd:integer)
Link from a Wikipage to another Wikipage	Greedy algorithm Lloyd's algorithm Locality-sensitive hashing Probabilistic roadmap Progressive scan Approximation algorithm Big O notation Sequence Voronoi Approximation algorithms Cluster analysis Computational geometry Geodesy Diameter Dijkstra's algorithm Doubling space Mesh generation Metric k-center Metric space P versus NP problem Phylogenetic diversity Pigeonhole principle Wireless sensor network Delaunay refinement Delone set Pixel Plane (geometry) Prefix Time complexity Triangle inequality Color quantization Computational geometry Heuristic (computer science) Hierarchical clustering Motion planning Data structure Finite element method Finite set Permutation Fault detection and isolation Halftone Johnson–Lindenstrauss lemma Travelling salesman problem Euclidean space Substring Largest empty sphere Point cloud Polygon mesh Randomized algorithm Range searching Rendering (computer graphics) Shortest path problem
has abstract	In computational geometry, the farthest-first traversal of a compact metric space is a sequence of points in the space, where the first point is selected arbitrarily and each successive point is as far as possible from the set of previously-selected points. The same concept can also be applied to a finite set of geometric points, by restricting the selected points to belong to the set or equivalently by considering the finite metric space generated by these points. For a finite metric space or finite set of geometric points, the resulting sequence forms a permutation of the points, also known as the greedy permutation. Every prefix of a farthest-first traversal provides a set of points that is widely spaced and close to all remaining points. More precisely, no other set of equally many points can be spaced more than twice as widely, and no other set of equally many points can be less than half as far to its farthest remaining point. In part because of these properties, farthest-point traversals have many applications, including the approximation of the traveling salesman problem and the metric k-center problem. They may be constructed in polynomial time, or (for low-dimensional Euclidean spaces) approximated in near-linear time. (en)
foaf:isPrimaryTopicOf	http://en.wikipedia.org/wiki/Farthest-first_traversal
is Link from a Wikipage to another Wikipage of	Lloyd's algorithm Metric k-center Delaunay triangulation Delone set Facility location problem Largest empty sphere
is foaf:primaryTopic of	http://en.wikipedia.org/wiki/Farthest-first_traversal

Faceted Search & Find service v1.17_git151 as of Feb 20 2025

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3240 as of Nov 11 2024, on Linux (x86_64-ubuntu_focal-linux-gnu), Single-Server Edition (72 GB total memory, 1 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2025 OpenLink Software