Smallest-circle problem (original) (raw)
En algorithmique et en géométrie, le problème du cercle minimum consiste à trouver le cercle le plus petit contenant un ensemble de points d'un plan. On peut étendre ce problème à trois dimensions, il s'agit alors de trouver la sphère minimum contenant les points, voire à d dimensions (d > 3), il s'agit alors d'hypersphères.
| Property | Value |
|---|---|
| dbo:abstract | El problema del círculo mínimo (también conocido como el problema del círculo de recubrimiento mínimo) es una cuestión matemática, consistente en calcular la circunferencia más pequeña que contiene todo un conjunto de puntos dado en el plano. El problema correspondiente en el espacio n-dimensional, implica determinar la n-esfera más pequeña que contiene todos los puntos de un conjunto dado. El problema del círculo mínimo fue propuesto inicialmente por el matemático inglés James Joseph Sylvester en 1857. En el plano es un ejemplo de un problema de (el ) en el que se debe elegir la ubicación de una nueva instalación para proporcionar servicio a un determinado número de clientes, minimizando la distancia más larga que cualquier cliente debe recorrer para alcanzar el nueva instalación. Tanto el problema de círculo mínimo en el plano como el problema de la esfera mínima en cualquier espacio de dimensión superior finita se pueden resolver con rutinas en tiempo lineal. (es) En algorithmique et en géométrie, le problème du cercle minimum consiste à trouver le cercle le plus petit contenant un ensemble de points d'un plan. On peut étendre ce problème à trois dimensions, il s'agit alors de trouver la sphère minimum contenant les points, voire à d dimensions (d > 3), il s'agit alors d'hypersphères. (fr) The smallest-circle problem (also known as minimum covering circle problem, bounding circle problem, smallest enclosing circle problem) is a mathematical problem of computing the smallest circle that contains all of a given set of points in the Euclidean plane. The corresponding problem in n-dimensional space, the smallest bounding sphere problem, is to compute the smallest n-sphere that contains all of a given set of points. The smallest-circle problem was initially proposed by the English mathematician James Joseph Sylvester in 1857. The smallest-circle problem in the plane is an example of a facility location problem (the 1-center problem) in which the location of a new facility must be chosen to provide service to a number of customers, minimizing the farthest distance that any customer must travel to reach the new facility. Both the smallest circle problem in the plane, and the smallest bounding sphere problem in any higher-dimensional space of bounded dimension are solvable in worst-case linear time. (en) Задача о наименьшей окружности или задача о минимальном покрывающем круге — задача о вычислении наименьшей окружности, содержащей все заданные точки из множества на евклидовой плоскости.Соответствующая задача в n-мерном пространстве, задача о наименьшей ограничивающей сфере, вычисляет наименьшую гиперсферу, содержащую все точки заданного множества. Задачу о наименьшей окружности первым поставил английский математик Джеймс Джозеф Сильвестр в 1857. Задача о наименьшей окружности на плоскости является примером задачи о размещении объектов (задача об 1-центре), в которой расположение новой организации нужно выбрать так, чтобы обслужить заданное множество клиентов с минимизацией максимального расстояния, которое должен преодолеть клиент, чтобы добраться до организации. Как задача о наименьшей окружности на плоскости, так и задача о наименьшей ограничивающей гиперсфере в более высоких размерностях разрешимы за линейное время. (ru) Зада́ча про найме́нше ко́ло або зада́ча про мініма́льне покривне́ ко́ло — задача про відшукання найменшого кола, яке містить всі задані точки з множини на евклідовій площині. Відповідна задача в n-вимірному просторі, задача про найменшу обмежувальну сферу, знаходить найменшу гіперсферу, яка містить усі точки заданої множини. Задачу про найменше коло 1857 року першим поставив англійський математик Джеймс Джозеф Сильвестр. Завдання про найменше коло на площині — це приклад задачі про розміщення об'єктів (задача про 1-центр), у якій розташування нової організації потрібно вибрати так, щоб обслужити задану множину клієнтів з мінімізацією максимальної відстані, яку має подолати клієнт, щоб дістатися до організації. Як задачу про найменше коло на площині, так і задачу про найменшу обмежувальну гіперсферу у вищих розмірностях можна розв'язати за лінійний час. (uk) 最小圆覆盖是数学中的一个算法，研究如何寻找能够覆盖平面上一群点的最小圆。这个问题在一般的n维空间中的推广是的问题，即寻找能覆盖n维空间中某个点集的最小球。最小圆覆盖问题最早由十九世纪的英国数学家詹姆斯·约瑟夫·西尔维斯特在1857年提出。 最小圆覆盖也是运筹学中的一种。广义的设施选址问题研究的是当已知一些目标点（仓库、销售终端、供应商等等）的位置时，求满足与这些目标点的距离相关的点的某些极值。最小圆覆盖可以看作是研究“到一些点的距离之最大值最小的点”的问题。现有的算法可以在线性时间内计算最小圆覆盖或最小包围球的问题。 (zh) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Smallest_circle_problem.svg?width=300 |
| dbo:wikiPageExternalLink | http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Bounding_volumes/Chapter_main.html https://github.com/hbf/miniball http://www.inf.ethz.ch/personal/gaertner/miniball.html |
| dbo:wikiPageID | 14355284 (xsd:integer) |
| dbo:wikiPageLength | 20136 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1117585122 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:N-dimensional_space dbr:Jung's_Theorem dbr:Uniform_distribution_(continuous) dbr:Line_segment dbr:Worst-case_complexity dbr:1-center_problem dbc:Combinatorial_optimization dbr:Obtuse_triangle dbr:Circle dbr:Bounding_sphere dbr:N-sphere dbr:Conjecture dbr:Convex_hull dbr:Line_(geometry) dbr:Linear_time dbr:Closest_string dbr:Emo_Welzl dbr:Empty_set dbr:Point_(geometry) dbr:C_(programming_language) dbr:Circumcircle dbr:Circumsphere dbr:Linear_programming dbr:Local_search_(optimization) dbc:Circles dbc:Computational_geometry dbr:Fortran dbr:Nimrod_Megiddo dbr:Mathematical_problem dbr:Radius dbr:Intersection_(set_theory) dbr:James_Joseph_Sylvester dbr:Tetrahedron dbr:LP-type_problem dbr:Bisection dbr:Triangle dbr:Diameter dbr:Circumscribed_circle dbr:The_plane dbr:Randomized_algorithm dbr:Set_(mathematics) dbr:Euclidean_plane dbr:Facility_location_problem dbr:Factorial dbr:Raimund_Seidel dbr:Subset dbr:Quadratic_program dbr:Smallest_bounding_sphere dbr:Smallest_enclosing_sphere dbr:Randomly_selected dbr:Recursive_algorithm dbr:Expected_time dbr:Subexponential_time dbr:File:Smallest_circle_problem.svg dbr:File:Megiddo's_minimum_enclosing_circle_algorithm_prune_stage2.png dbr:File:The_smallest_enclosing_disk_of_points_in_the_plane_is_unique.svg |
| dbp:wikiPageUsesTemplate | dbt:Harvtxt dbt:Math dbt:Reflist dbt:Sfn dbt:Short_description dbt:Var dbt:Collapse_bottom dbt:Collapse_top |
| dct:subject | dbc:Combinatorial_optimization dbc:Circles dbc:Computational_geometry |
| gold:hypernym | dbr:Problem |
| rdf:type | yago:WikicatCircles yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Attribute100024264 yago:Circle113873502 yago:ConicSection113872975 yago:Ellipse113878306 yago:Event100029378 yago:Figure113862780 yago:PlaneFigure113863186 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:WikicatGeometricAlgorithms yago:YagoPermanentlyLocatedEntity dbo:Disease yago:Rule105846932 yago:Shape100027807 |
| rdfs:comment | En algorithmique et en géométrie, le problème du cercle minimum consiste à trouver le cercle le plus petit contenant un ensemble de points d'un plan. On peut étendre ce problème à trois dimensions, il s'agit alors de trouver la sphère minimum contenant les points, voire à d dimensions (d > 3), il s'agit alors d'hypersphères. (fr) 最小圆覆盖是数学中的一个算法，研究如何寻找能够覆盖平面上一群点的最小圆。这个问题在一般的n维空间中的推广是的问题，即寻找能覆盖n维空间中某个点集的最小球。最小圆覆盖问题最早由十九世纪的英国数学家詹姆斯·约瑟夫·西尔维斯特在1857年提出。 最小圆覆盖也是运筹学中的一种。广义的设施选址问题研究的是当已知一些目标点（仓库、销售终端、供应商等等）的位置时，求满足与这些目标点的距离相关的点的某些极值。最小圆覆盖可以看作是研究“到一些点的距离之最大值最小的点”的问题。现有的算法可以在线性时间内计算最小圆覆盖或最小包围球的问题。 (zh) El problema del círculo mínimo (también conocido como el problema del círculo de recubrimiento mínimo) es una cuestión matemática, consistente en calcular la circunferencia más pequeña que contiene todo un conjunto de puntos dado en el plano. El problema correspondiente en el espacio n-dimensional, implica determinar la n-esfera más pequeña que contiene todos los puntos de un conjunto dado. El problema del círculo mínimo fue propuesto inicialmente por el matemático inglés James Joseph Sylvester en 1857. (es) The smallest-circle problem (also known as minimum covering circle problem, bounding circle problem, smallest enclosing circle problem) is a mathematical problem of computing the smallest circle that contains all of a given set of points in the Euclidean plane. The corresponding problem in n-dimensional space, the smallest bounding sphere problem, is to compute the smallest n-sphere that contains all of a given set of points. The smallest-circle problem was initially proposed by the English mathematician James Joseph Sylvester in 1857. (en) Задача о наименьшей окружности или задача о минимальном покрывающем круге — задача о вычислении наименьшей окружности, содержащей все заданные точки из множества на евклидовой плоскости.Соответствующая задача в n-мерном пространстве, задача о наименьшей ограничивающей сфере, вычисляет наименьшую гиперсферу, содержащую все точки заданного множества. Задачу о наименьшей окружности первым поставил английский математик Джеймс Джозеф Сильвестр в 1857. (ru) Зада́ча про найме́нше ко́ло або зада́ча про мініма́льне покривне́ ко́ло — задача про відшукання найменшого кола, яке містить всі задані точки з множини на евклідовій площині. Відповідна задача в n-вимірному просторі, задача про найменшу обмежувальну сферу, знаходить найменшу гіперсферу, яка містить усі точки заданої множини. Задачу про найменше коло 1857 року першим поставив англійський математик Джеймс Джозеф Сильвестр. (uk) |
| rdfs:label | Problema del círculo mínimo (es) Problème du cercle minimum (fr) Smallest-circle problem (en) Задача о наименьшей окружности (ru) Задача про найменше коло (uk) 最小圆覆盖 (zh) |
| owl:sameAs | freebase:Smallest-circle problem yago-res:Smallest-circle problem wikidata:Smallest-circle problem dbpedia-es:Smallest-circle problem dbpedia-fa:Smallest-circle problem dbpedia-fr:Smallest-circle problem dbpedia-ru:Smallest-circle problem dbpedia-uk:Smallest-circle problem dbpedia-zh:Smallest-circle problem https://global.dbpedia.org/id/2S7AK |
| prov:wasDerivedFrom | wikipedia-en:Smallest-circle_problem?oldid=1117585122&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Smallest_circle_problem.svg wiki-commons:Special:FilePath/Megiddo's_minimum_enclosing_circle_algorithm_prune_stage2.png wiki-commons:Special:FilePath/The_smallest_enclosin..._of_points_in_the_plane_is_unique.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Smallest-circle_problem |
| is dbo:wikiPageRedirects of | dbr:Smallest_circle_problem dbr:Smallest_enclosing_circle dbr:Minimal_bounding_circle dbr:Minimal_enclosing_circle dbr:Bounding_circle |
| is dbo:wikiPageWikiLink of | dbr:Curve_of_constant_width dbr:Combinatorial_Geometry_in_the_Plane dbr:Jung's_theorem dbr:Curve-shortening_flow dbr:Nimrod_Megiddo dbr:Parametric_search dbr:Chebyshev_center dbr:Four-vertex_theorem dbr:Circumscribed_sphere dbr:Smallest_circle_problem dbr:Smallest_enclosing_circle dbr:Minimal_bounding_circle dbr:Minimal_enclosing_circle dbr:Bounding_circle |
| is foaf:primaryTopic of | wikipedia-en:Smallest-circle_problem |
