Bin (computational geometry) (original) (raw)
In computational geometry, the bin is a data structure that allows efficient region queries. Each time a data point falls into a bin, the frequency of that bin is increased by one. For example, if there are some axis-aligned rectangles on a 2D plane, the structure can answer the question, "Given a query rectangle, what are the rectangles intersecting it?" In the example in the top figure, A, B, C, D, E and F are existing rectangles, so the query with the rectangle Q should return C, D, E and F, if we define all rectangles as closed intervals.
| Property | Value |
|---|---|
| dbo:abstract | In computational geometry, the bin is a data structure that allows efficient region queries. Each time a data point falls into a bin, the frequency of that bin is increased by one. For example, if there are some axis-aligned rectangles on a 2D plane, the structure can answer the question, "Given a query rectangle, what are the rectangles intersecting it?" In the example in the top figure, A, B, C, D, E and F are existing rectangles, so the query with the rectangle Q should return C, D, E and F, if we define all rectangles as closed intervals. The data structure partitions a region of the 2D plane into uniform-sized bins. The bounding box of the bins encloses all candidate rectangles to be queried. All the bins are arranged in a 2D array. All the candidates are represented also as 2D arrays. The size of a candidate's array is the number of bins it intersects. For example, in the top figure, candidate B has 6 elements arranged in a 3 row by 2 column array because it intersects 6 bins in such an arrangement. Each bin contains the head of a singly linked list. If a candidate intersects a bin, it is chained to the bin's linked list. Each element in a candidate's array is a link node in the corresponding bin's linked list. (en) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Bin_computational_geometry.png?width=300 |
| dbo:wikiPageID | 13764454 (xsd:integer) |
| dbo:wikiPageLength | 5775 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1076477845 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Arithmetic_right_shift dbr:Computational_geometry dbr:Plane_(geometry) dbc:Geometric_data_structures dbr:Data_structure dbr:K-d_tree dbr:Cartesian_Coordinate_System dbr:Closed_interval dbr:Quantization_(signal_processing) dbr:Hash_table dbr:Space_partitioning dbr:Singly_linked_list dbr:Bounding_box dbr:File:Bin_computational_geometry.png dbr:File:Gaussian_Histogram_10million_samples_100K_bins.png |
| dbp:wikiPageUsesTemplate | dbt:Other_uses dbt:Reflist dbt:See_also dbt:Technical |
| dct:subject | dbc:Geometric_data_structures |
| gold:hypernym | dbr:Structure |
| rdf:type | owl:Thing yago:Abstraction100002137 yago:Arrangement105726596 yago:Cognition100023271 yago:DataStructure105728493 yago:PsychologicalFeature100023100 yago:WikicatGeometricDataStructures dbo:Building yago:Structure105726345 |
| rdfs:comment | In computational geometry, the bin is a data structure that allows efficient region queries. Each time a data point falls into a bin, the frequency of that bin is increased by one. For example, if there are some axis-aligned rectangles on a 2D plane, the structure can answer the question, "Given a query rectangle, what are the rectangles intersecting it?" In the example in the top figure, A, B, C, D, E and F are existing rectangles, so the query with the rectangle Q should return C, D, E and F, if we define all rectangles as closed intervals. (en) |
| rdfs:label | Bin (computational geometry) (en) |
| rdfs:seeAlso | dbr:Histogram |
| owl:sameAs | freebase:Bin (computational geometry) yago-res:Bin (computational geometry) wikidata:Bin (computational geometry) dbpedia-sr:Bin (computational geometry) https://global.dbpedia.org/id/4Z7hU |
| prov:wasDerivedFrom | wikipedia-en:Bin_(computational_geometry)?oldid=1076477845&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Bin_computational_geometry.png wiki-commons:Special:FilePath/Gaussian_Histogram_10million_samples_100K_bins.png |
| foaf:isPrimaryTopicOf | wikipedia-en:Bin_(computational_geometry) |
| is dbo:wikiPageDisambiguates of | dbr:BIN |
| is dbo:wikiPageWikiLink of | dbr:BIN dbr:List_of_data_structures dbr:Quadrilateralized_spherical_cube dbr:Data_binning dbr:Terminal_Doppler_Weather_Radar dbr:C_dynamic_memory_allocation dbr:Space_partitioning |
| is foaf:primaryTopic of | wikipedia-en:Bin_(computational_geometry) |
