Envolvente convexa

Envoltura convexa de un conjunto de 8 puntos en el plano.

En matemáticas se define la envolvente convexa, envoltura convexa o cápsula convexa de un conjunto de puntos X de dimensión n como la intersección de todos los conjuntos convexos que contienen a X.[1]​

Dados k puntos su envolvente convexa C viene dada por la expresión:



En el caso particular de puntos en un plano, si no todos los puntos están alineados, entonces su envolvente convexa corresponde a un polígono convexo cuyos vértices son algunos de los puntos del conjunto inicial de puntos.

Una forma intuitiva de ver la envolvente convexa de un conjunto de puntos en el plano, es imaginar una banda elástica estirada que los encierra a todos. Cuando se libere la banda elástica tomará la forma de la envolvente convexa.

Alternativamente

La unión de todas las combinaciones convexas de conjuntos finitos de puntos de se denomina cápsula convexa de .[2]​

Teorema de Carathéodory

La cápsula convexa de un conjunto coincide con la unión de todas las combinaciones convexas posibles de subconjuntos finitos del conjunto que tienen a lo más puntos.[2]​

Cálculo de la envolvente convexa

En geometría computacional existen numerosos algoritmos para calcular la envolvente convexa de un conjunto finito de puntos, con diversos grados de complejidad computacional. La complejidad del algoritmo de resolución se suele estimar en función del número n de puntos de entrada, y el número h de puntos de la correspondiente envolvente convexa.

Algoritmos para el cálculo de la envolvente convexa en el plano

  • Jarvis march o gift wrapping algorithm: Propuesto por R. A. Jarvis en 1973. Es uno de los más simples y posee una complejidad computacional O(nh). En el peor de los casos su complejidad será O(n2).
  • Método de Graham: Publicado en 1972, es mucho más eficiente y posee una complejidad computacional O(n log n). Si los puntos se encuentran pre-ordenados por una de las coordenadas o por el ángulo a un vector fijo entonces la complejidad es O(n).
  • Quickhull: Un método recursivo creado de forma independiente en 1977 por W. Eddy y A. Bykat. Tiene una complejidad esperada O(n log n), pero que puede degenerar a O(n^2) en el peor caso.
  • Divide y vencerás (Divide and conquer): Otro algoritmo de complejidad O(n log n) publicado en 1977 por Franco P. Preparata y Hong. También es aplicable al caso tridimensional.[3]​

Referencias

  1. ↑ Weisstein, Eric W. «envolvente convexa». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research. 
  2. ↑ a b Boss, V. (2011). Álgebra lineal. Moscú: Editorial URSS. ISBN 978-5-396-00066-7. 
  3. ↑ Preparata, Franco P.; Hong, S.J. (1977). «Convex hulls of finite sets of points in two and three dimensions». Communications of the ACM 20 (2). doi:10.1145/359423.359430. 

Véase también

Convexidad

Read other articles:

Холокост на Украине

Часть серии статей о Холокосте Идеология и политика Расовая гигиена · Расовый антисемитизм · Нацистская расовая политика · Нюрнбергские расовые законы Шоа Лагеря смерти Белжец · Дахау · Майданек · Малый Тростенец · Маутхаузен ·&...

 

Charity Shield FA 1929

Charity Shield FA 1929TurnamenCharity Shield FA English Professionals XI English Amateurs XI 3 0 Tanggal7 Oktober 1929StadionThe Den, London← 1928 1930 → Charity Shield FA 1929 adalah pertandingan sepak bola antara English Professionals XI dan English Amateurs XI yang diselenggarakan pada 7 Oktober 1929 di The Den, London. Pertandingan ini merupakan pertandingan ke-16 dari penyelenggaraan Charity Shield FA. Pertandingan ini dimenangkan oleh English Professionals XI dengan skor 3�...

 

2312 (novel)

Novel by Kim Stanley Robinson 2312 First editionAuthorKim Stanley RobinsonCover artistKirk BenshoffCountryUnited StatesLanguageEnglishGenreScience fictionPublisherOrbitPublication dateMay 23, 2012Media typePrint (hardcover and electronic book) and audio-CDPages576AwardsNebula Award for Best NovelISBN978-0-316-09812-0 2312 is a hard science fiction novel by American writer Kim Stanley Robinson, published in 2012. It is set in the year 2312 when society has spread out across the Solar...

Idolâtrie

L'Adoration du Veau d'Or par Nicolas Poussin. Le terme d'idolâtrie désigne l'adoration réelle ou supposée d'une image, d'un astre, d'une idée, d'un objet ou d'une personnalité. Pour les religions abrahamiques, l'idolâtrie est une corruption, une impiété à combattre : le terme est donc devenu péjoratif ou synonyme de superstition et d'égarement. L'animisme et le polythéisme, qualifiés de paganisme, sont ainsi supposés adorer non pas des esprits ou des divinités, mais l...

 

Daftar genealogi dalam Alkitab

Berikut ini adalah genealogi yang dicatat di dalam Alkitab sejak manusia pertama, Adam diciptakan. Kitab Taurat Keturunan Adam dan Hawa Genealogi Adam hingga Nuh (Kejadian 4:17–22; 5:1–32; 1Tawarikh 1)         Adam Hawa                                       ...

 

Chickaloon (Alaska)

Cet article est une ébauche concernant une localité de l'Alaska. Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants. Pour les articles homonymes, voir Chickaloon. Chickaloon Administration Pays États-Unis État Alaska Borough Borough de Matanuska-Susitna Code FIPS 02-12340 GNIS 1400239 Démographie Population 272 hab. (2010) Densité 1,3 hab./km2 Géographie Coordonnées 61° 47′ 38″ ...

Unione Sportiva Savoia 1926-1927

Voce principale: Associazione Calcio Savoia 1908. Unione Sportiva SavoiaStagione 1926-1927Sport calcio Squadra Savoia Allenatore Carlino Presidente Teodoro Voiello Seconda Divisione1º posto (Girone Campano)1º posto (Girone finale) Coppa ItaliaPrimo turno Maggiori presenzeCampionato: Giraud I, Orsini I, Orsini II, Rescigno (8)Totale: Giraud I, Orsini I, Orsini II, Rescigno (8) Miglior marcatoreCampionato: Maresca (11)Totale: Maresca (11) StadioCampo Oncino 1924-1925 1927-1928 Si invita...

 

2 Tawarikh 6

2 Tawarikh 6Kitab Tawarikh (Kitab 1 & 2 Tawarikh) lengkap pada Kodeks Leningrad, dibuat tahun 1008.KitabKitab 2 TawarikhKategoriKetuvimBagian Alkitab KristenPerjanjian LamaUrutan dalamKitab Kristen14← pasal 5 pasal 7 → 2 Tawarikh 6 (atau II Tawarikh 6, disingkat 2Taw 6) adalah bagian dari Kitab 2 Tawarikh dalam Alkitab Ibrani dan Perjanjian Lama di Alkitab Kristen. Dalam Alkitab Ibrani termasuk dalam bagian Ketuvim (כְּתוּבִים, tulisan).[1][2] Teks Na...

 

1945 Maltese general election

1945 Maltese general election ← 1939 10-12 November 1945 1947 → 10 seats in the Parliament of Malta6 seats needed for a majority Party Leader % Seats +/– Labour Paul Boffa 76.20 9 +8 Independent 23.80 1 +1 This lists parties that won seats. See the complete results below. Politics of Malta Republic Constitution President (list) George Vella Government Prime Minister (list) Robert Abela Deputy Prime Minister (list) Chris Fearne Cabinet (current) Parliament Speaker (list...

Kappa Cassiopeiae

Star in the constellation Cassiopeia κ Cassiopeiae Location of κ Cassiopeiae (circled) Observation dataEpoch J2000.0      Equinox J2000.0 Constellation Cassiopeia Right ascension 00h 32m 59.991s[1] Declination +62° 55′ 54.42″[1] Apparent magnitude (V) 4.12 - 4.21[2] Characteristics Spectral type BC0.7 Ia[3] Apparent magnitude (U) 3.50[4] Apparent magnitude (B) 4.276...

 

5x5 The Best Selection of 2002-2004

5x5 The Best Selection of 2002-2004Album hit terbaik karya ArashiDirilis10 November 2004 (2004-11-10)Direkam2002-2004GenrePopDurasi70:13 (Edisi terbatas)74:21 (Edisi regular)LabelJ StormJACA-5019 (CD-DVD Edisi terbatas)JACA-5020 (Edisi regular)Kronologi Arashi Iza, Now!(2004)String Module Error: Match not found2004 5x5 The Best Selection of 2002-2004(2004) One(2004)String Module Error: Match not found2004 Singel dalam album 5x5 The Best Selection of 2002-2004 Hitomi no Naka no Galaxy...

 

Halländska

Halländska Halländska är de dialekter inom svenska som talas i landskapet Halland. Södra Halland anses tillhöra det skånska språkområdet, och är sålunda historiskt sett en östdansk, alternativt sydskandinavisk dialekt.[1] Halländskan närmar sig i dialektområdets nordliga delar västgötska och göteborgska. Kännetecken I likhet med andra östdanska/sydsvenska dialekter har konsonanterna p, t, k efter lång vokal i nästan hela landskapet övergått till b, d, g (sv. kaka → ka...

Dermatite atopique

Pour les articles homonymes, voir eczéma. Dermatite atopique Dermatite atopique Données clés Symptômes Réaction allergique (en) et dermatite Traitement Médicament Pimecrolimus, cidoxepin (en), methdilazine (en), triprolidine, bétaméthasone, tacrolimus, fluocinolone (en), alimémazine, désonide et abrocitinib (en) Spécialité Dermatologie Classification et ressources externes CISP-2 S87 CIM-10 L20 CIM-9 691.8 OMIM 603165 DiseasesDB 4113 MedlinePlus 000853 eMedicine 762045derm/38 ped...

 

西遊記大結局之仙履奇緣

本條目存在以下問題，請協助改善本條目或在討論頁針對議題發表看法。 此條目需要編修，以確保文法、用詞、语气、格式、標點等使用恰当。 (2013年8月6日)請按照校對指引，幫助编辑這個條目。（幫助、討論） 此條目剧情、虛構用語或人物介紹过长过细，需清理无关故事主轴的细节、用語和角色介紹。 (2020年10月6日)劇情、用語和人物介紹都只是用於了解故事主軸，輔助�...

 

لبنان الاشتراكي

يفتقر محتوى هذه المقالة إلى الاستشهاد بمصادر. فضلاً، ساهم في تطوير هذه المقالة من خلال إضافة مصادر موثوق بها. أي معلومات غير موثقة يمكن التشكيك بها وإزالتها. (مارس 2016) لبنان الاشتراكي حركة سياسية لبنانية ذات توجه ماركسي أسست سنة 1965. من أهم قادتها أحمد بيضون، وضاح شرارة، فواز...

Mario Bauzá

Cuban-American musician, composer, and founder of Afro-Cuban Jazz This article includes a list of general references, but it lacks sufficient corresponding inline citations. Please help to improve this article by introducing more precise citations. (July 2021) (Learn how and when to remove this message) Mario BauzáMario Bauzá, taken in Brooklyn, New York, 1992Background informationBirth namePrudencio Mario Bauzá Cárdenas[citation needed]Born(1911-04-28)April 28, 1911Havana, CubaDi...

 

Omar Chehade

Peruvian lawyer and politician, Second Vice President of Peru from 2011 to 2012 This article needs to be updated. Please help update this article to reflect recent events or newly available information. (March 2024) In this Spanish name, the first or paternal surname is Chehade and the second or maternal family name is Moya. Omar ChehadeChehade in December 2011Member of CongressIn office16 March 2020 – 26 July 2021ConstituencyLimaIn office26 July 2011 – 26 July 2...

 

Sharana Airstrip

Airport in AfghanistanSharana Airstrip د شرنی هوائی ډګرIATA: OASICAO: OASASummaryAirport typePublicServesSharana, Paktika ProvinceLocation AfghanistanElevation AMSL7,435 ft / 2,266 mCoordinates33°07′33″N 068°50′19″E / 33.12583°N 68.83861°E / 33.12583; 68.83861 (Sharana Airstrip (Sharana))MapOASLocation of Sharana Airstrip in AfghanistanRunways Direction Length Surface m ft 14/32 1,300 4,265 Asphalt Sources: Landings....

Conservation psychology

This article includes a list of general references, but it lacks sufficient corresponding inline citations. Please help to improve this article by introducing more precise citations. (August 2008) (Learn how and when to remove this message) Conservation psychology is the scientific study of the reciprocal relationships between humans and the rest of nature, with a particular focus on how to encourage conservation of the natural world.[1] Rather than a specialty area within psychology ...

 

自動車工学

この記事は英語版の対応するページを翻訳することにより充実させることができます。（2024年6月）翻訳前に重要な指示を読むには右にある[表示]をクリックしてください。 英語版記事を日本語へ機械翻訳したバージョン（Google翻訳）。 万が一翻訳の手がかりとして機械翻訳を用いた場合、翻訳者は必ず翻訳元原文を参照して機械翻訳の誤りを訂正し、正確な翻訳にし�...