Range searching (original) (raw)
In computer science, the range searching problem consists of processing a set S of objects, in order to determine which objects from S intersect with a query object, called the range. For example, if S is a set of points corresponding to the coordinates of several cities, find the subset of cities within a given range of latitudes and longitudes. The range searching problem and the data structures that solve it are a fundamental topic of computational geometry. Applications of the problem arise in areas such as geographical information systems (GIS), computer-aided design (CAD) and databases.
| Property | Value |
|---|---|
| dbo:abstract | La búsqueda de rango consiste, en su forma más general, en realizar un preprocesamiento a un conjunto S de objetos con el objetivo de determinar cuáles de estos se intersecan con otro objeto denominado rango. Por ejemplo, S puede ser un conjunto de puntos correspondientes a las coordenadas de varias ciudades, y queremos encontrar aquellas que se encuentran dentro de un determinado rango de longitud y latitud. Los problemas y estructura de datos de la búsqueda de rango son una temática fundamental de la Geometría computacional. El problema de la búsqueda de rango tiene aplicaciones no solo en áreas relacionadas con el procesamiento de datos geométricos (como sistema de información geográfica o diseño asistido por computadora), sino también en bases de datos. (es) Dans sa forme la plus générale, la recherche par plage consiste à traiter un ensemble S d'objets dans le but de déterminer lesquels sont situés à l'intérieur d'un domaine, appelé la plage de recherche. Par exemple, S peut être un ensemble de points représentant les coordonnées de villes, et l'on peut chercher quelles sont les villes situées à moins de 50 km des côtes, ou quelles sont les villes situées à moins de 100 km d'une ville donnée. La recherche par plage est un problème fondamental en géométrie algorithmique et pour la gestion des bases de données. Les applications sont nombreuses, particulièrement pour les systèmes d'information géographiques (SIG), ou pour les programmes de dessin assisté par ordinateur (DAO). Si on considère des domaines de recherche rectangulaires, le problème s'étend facilement à des questions non-géométriques. Par exemple, "quels sont les individus entre 20 et 30 ans habitant Paris et gagnant plus de 1500 euros par mois ?". (fr) In computer science, the range searching problem consists of processing a set S of objects, in order to determine which objects from S intersect with a query object, called the range. For example, if S is a set of points corresponding to the coordinates of several cities, find the subset of cities within a given range of latitudes and longitudes. The range searching problem and the data structures that solve it are a fundamental topic of computational geometry. Applications of the problem arise in areas such as geographical information systems (GIS), computer-aided design (CAD) and databases. (en) |
| dbo:thumbnail | wiki-commons:Special:FilePath/SimplexRangeSearching.svg?width=300 |
| dbo:wikiPageExternalLink | https://archive.org/details/computationalgeo00berg https://refubium.fu-berlin.de/handle/fub188/17795 |
| dbo:wikiPageID | 9334818 (xsd:integer) |
| dbo:wikiPageLength | 10974 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1093071244 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Bernard_Chazelle dbr:Jon_Bentley_(computer_scientist) dbr:Dynamization dbr:Line_segment dbr:Commutative dbc:Database_theory dbr:Geographic_information_system dbr:Range_tree dbr:Circle dbr:Dan_Willard dbr:Timothy_M._Chan dbr:Line_(geometry) dbr:Longitude dbr:Simplex dbr:Computational_geometry dbr:Computer-aided_design dbr:Computer_science dbr:Half-space_(geometry) dbr:Point_(geometry) dbr:Polygon dbc:Geometric_data_structures dbr:Data_structure dbr:K-d_tree dbr:Semigroup dbr:Database dbr:Fractional_cascading dbr:ACM_Computing_Surveys dbr:Latitude dbr:Big_O_notation dbr:Sphere dbr:Infinity dbr:Kurt_Mehlhorn dbr:Mihai_Pătrașcu_(computer_scientist) dbr:Categorical_variable dbr:Rectangle dbr:Model_of_computation dbr:Pointer_machine dbr:Range_query dbr:Word_RAM dbr:Range_query_(database) dbr:Range_reporting dbr:Axis-aligned_rectangle dbr:Asymptotically_optimal dbr:File:SimplexRangeSearching.svg dbr:File:Orthogonal_range_query.svg |
| dbp:wikiPageUsesTemplate | dbt:Citation dbt:Reflist |
| dcterms:subject | dbc:Database_theory dbc:Geometric_data_structures |
| rdf:type | yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Arrangement105726596 yago:Cognition100023271 yago:DataStructure105728493 yago:Event100029378 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:WikicatGeometricAlgorithms yago:WikicatGeometricDataStructures yago:YagoPermanentlyLocatedEntity yago:Rule105846932 yago:Structure105726345 |
| rdfs:comment | In computer science, the range searching problem consists of processing a set S of objects, in order to determine which objects from S intersect with a query object, called the range. For example, if S is a set of points corresponding to the coordinates of several cities, find the subset of cities within a given range of latitudes and longitudes. The range searching problem and the data structures that solve it are a fundamental topic of computational geometry. Applications of the problem arise in areas such as geographical information systems (GIS), computer-aided design (CAD) and databases. (en) La búsqueda de rango consiste, en su forma más general, en realizar un preprocesamiento a un conjunto S de objetos con el objetivo de determinar cuáles de estos se intersecan con otro objeto denominado rango. Por ejemplo, S puede ser un conjunto de puntos correspondientes a las coordenadas de varias ciudades, y queremos encontrar aquellas que se encuentran dentro de un determinado rango de longitud y latitud. (es) Dans sa forme la plus générale, la recherche par plage consiste à traiter un ensemble S d'objets dans le but de déterminer lesquels sont situés à l'intérieur d'un domaine, appelé la plage de recherche. Par exemple, S peut être un ensemble de points représentant les coordonnées de villes, et l'on peut chercher quelles sont les villes situées à moins de 50 km des côtes, ou quelles sont les villes situées à moins de 100 km d'une ville donnée. (fr) |
| rdfs:label | Búsqueda de rango (es) Recherche par plage (fr) Range searching (en) |
| owl:sameAs | freebase:Range searching yago-res:Range searching wikidata:Range searching dbpedia-es:Range searching dbpedia-fa:Range searching dbpedia-fr:Range searching dbpedia-vi:Range searching https://global.dbpedia.org/id/39pYe |
| prov:wasDerivedFrom | wikipedia-en:Range_searching?oldid=1093071244&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/SimplexRangeSearching.svg wiki-commons:Special:FilePath/Orthogonal_range_query.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Range_searching |
| is dbo:wikiPageRedirects of | dbr:Orthogonal_range_searching dbr:Range_search |
| is dbo:wikiPageWikiLink of | dbr:List_of_combinatorial_computational_geometry_topics dbr:Privacy-preserving_computational_geometry dbr:All_nearest_smaller_values dbr:List_of_books_in_computational_geometry dbr:Range_tree dbr:R-tree dbr:Dan_Willard dbr:Range_query_(data_structures) dbr:Sauer–Shelah_lemma dbr:Computational_geometry dbr:Emo_Welzl dbr:Fractional_cascading dbr:Farthest-first_traversal dbr:Heilbronn_triangle_problem dbr:Cartesian_tree dbr:Range_query_(database) dbr:Orthogonal_range_searching dbr:Range_search |
| is foaf:primaryTopic of | wikipedia-en:Range_searching |
