| dbo:abstract |
In computational geometry, Klee's measure problem is the problem of determining how efficiently the measure of a union of (multidimensional) rectangular ranges can be computed. Here, a d-dimensional rectangular range is defined to be a Cartesian product of d intervals of real numbers, which is a subset of Rd. The problem is named after Victor Klee, who gave an algorithm for computing the length of a union of intervals (the case d = 1) which was later shown to be optimally efficient in the sense of computational complexity theory. The computational complexity of computing the area of a union of 2-dimensional rectangular ranges is now also known, but the case d ≥ 3 remains an open problem. (en) En la geometría computacional, el problema de la medida de Klee es el problema de determinar cuan eficientemente la medida de una unión (multidimensional) de rangos rectangulares puede ser calculada. Aquí, un rango rectangular d-dimensional es definido como un producto cartesiano de d intervalos de números reales, que es un subconjunto de Rd. Este problema toma el nombre en honor a Victor Klee, quien dio un algoritmo para calcular la longitud de una unión de intervalos (el caso d = 1)que más tarde mostró ser óptimamente eficiente en el sentido de la teoría de complejidad computacional. La complejidad computacional para calcular el área de una unión de rangos rectangulares 2-dimensionales ahora también es conocida, pero en el caso de d ≥ 3 sigue siendo un problema abierto. (es) |
| dbo:thumbnail |
wiki-commons:Special:FilePath/Set_a_rectangles_(Klee's_Trevis).svg?width=300 |
| dbo:wikiPageExternalLink |
https://web.archive.org/web/20100613104635/http:/compgeom.cs.uiuc.edu/~jeffe/open/klee.html https://web.archive.org/web/20100618011523/http:/compgeom.cs.uiuc.edu/~jeffe/open/ https://archive.org/details/sofsem98theorypr0000sofs/page/304 https://cs.uwaterloo.ca/~tmchan/easyklee4_13.pdf%7Cisbn=978-0-7695-5135-7%7Cciteseerx=10.1.1.643.26%7Cs2cid=11648588 |
| dbo:wikiPageID |
3107845 (xsd:integer) |
| dbo:wikiPageLength |
8509 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID |
991845497 (xsd:integer) |
| dbo:wikiPageWikiLink |
dbr:Cartesian_product dbr:Algorithm dbc:Mathematical_problems dbr:Jon_Bentley_(computer_scientist) dbr:Victor_Klee dbr:Analysis_of_algorithms dbr:Measure_(mathematics) dbr:Quadtree dbr:Convex_body dbr:Convex_volume_approximation dbr:SIAM_Journal_on_Computing dbr:Lower_bound dbr:Communications_of_the_ACM dbr:Computational_complexity_theory dbr:Computational_geometry dbr:Computer_graphics dbr:Franco_P._Preparata dbr:Michael_Fredman dbr:Lecture_Notes_in_Computer_Science dbr:Open_problem dbr:American_Mathematical_Monthly dbc:Computational_geometry dbr:Interval_(mathematics) dbr:Jan_van_Leeuwen dbr:Area_(geometry) dbc:Measure_theory dbr:Big_O_notation dbr:Trellis_(graph) dbr:Dimension dbr:Mark_Overmars dbr:Real_number dbr:Rectangle dbr:Michael_Ian_Shamos dbr:Sorting dbr:Union_(set_theory) dbr:Real_line dbr:Subset dbr:Kd-tree dbr:File:Set_a_rectangles_(Klee's_Trevis).svg |
| dbp:wikiPageUsesTemplate |
dbt:Citation dbt:Reflist |
| dct:subject |
dbc:Mathematical_problems dbc:Computational_geometry dbc:Measure_theory |
| gold:hypernym |
dbr:Problem |
| rdf:type |
yago:WikicatMathematicalProblems yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Attribute100024264 yago:Condition113920835 yago:Difficulty114408086 yago:Event100029378 yago:Problem114410605 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:WikicatGeometricAlgorithms yago:YagoPermanentlyLocatedEntity dbo:Disease yago:Rule105846932 yago:State100024720 |
| rdfs:comment |
In computational geometry, Klee's measure problem is the problem of determining how efficiently the measure of a union of (multidimensional) rectangular ranges can be computed. Here, a d-dimensional rectangular range is defined to be a Cartesian product of d intervals of real numbers, which is a subset of Rd. (en) En la geometría computacional, el problema de la medida de Klee es el problema de determinar cuan eficientemente la medida de una unión (multidimensional) de rangos rectangulares puede ser calculada. Aquí, un rango rectangular d-dimensional es definido como un producto cartesiano de d intervalos de números reales, que es un subconjunto de Rd. (es) |
| rdfs:label |
Problema de la medida de Klee (es) Klee's measure problem (en) |
| owl:sameAs |
freebase:Klee's measure problem yago-res:Klee's measure problem wikidata:Klee's measure problem dbpedia-es:Klee's measure problem https://global.dbpedia.org/id/4pVFQ |
| prov:wasDerivedFrom |
wikipedia-en:Klee's_measure_problem?oldid=991845497&ns=0 |
| foaf:depiction |
wiki-commons:Special:FilePath/Set_a_rectangles_(Klee's_Trevis).svg |
| foaf:isPrimaryTopicOf |
wikipedia-en:Klee's_measure_problem |
| is dbo:knownFor of |
dbr:Victor_Klee |
| is dbo:wikiPageDisambiguates of |
dbr:Measure_problem |
| is dbo:wikiPageRedirects of |
dbr:Bentley's_algorithm dbr:Klee_measure_problem |
| is dbo:wikiPageWikiLink of |
dbr:List_of_combinatorial_computational_geometry_topics dbr:Jon_Bentley_(computer_scientist) dbr:Victor_Klee dbr:Convex_volume_approximation dbr:Michael_Fredman dbr:K-d_tree dbr:Measure_problem dbr:Octree dbr:Bentley's_algorithm dbr:Klee_measure_problem |
| is foaf:primaryTopic of |
wikipedia-en:Klee's_measure_problem |
