Share to: share facebook share twitter share wa share telegram print page

Geometria computacional

XenoCollide

Geometria Computacional é um ramo da Ciência da Computação que estuda algoritmos e estruturas de dados para a resolução computacional de problemas geométricos. Além disso, alguns problemas puramente geométricos surgem do estudo de algoritmos e, por isso, também são considerados parte da geometria computacional.

Os problemas em Geometria Computacional são tratados em termos de objetos geométricos elementares como pontos, retas, segmentos de reta, polígonos, etc. Em geral, o objetivo desta disciplina é resolver os problemas geométricos de forma eficiente, isto é, utilizando o menor número possível de operações simples sobre os elementos geométricos. A Geometria Computacional dá ênfase a complexidade computacional dos problemas e algoritmos estudados.

A Geometria Computacional emergiu de áreas de desenvolvimento e análise de algoritmos em meados da década de 1970. O primeiro uso do termo Geometria Computacional com este sentido ocorreu em 1975.[1]

A geometria computacional estuda tanto problemas geométricos clássicos, como também problemas motivados por diversas áreas da computação como Computação Gráfica, desenho assistido por computador (CAD/CAM), robótica, sistemas de informação geográfica, visão computacional, otimização combinatória, processamento de imagens, teoria dos grafos, desenho de circuitos integrados, aprendizagem de máquina etc.

Principais problemas

Muitos problemas de Geometria Computacional têm enunciados simples e várias soluções possíveis, desde as mais ingênuas até as mais eficientes. Alguns exemplos de problemas algorítmicos são listados abaixo.

Enquanto os problemas acimas possuem uma entrada fixa e uma saída construída em função da entrada, outros problemas geométricos são definidos em termos de consultas geométricas. Nestes problemas o objetivo é organizar os dados de modo a responder eficientemente múltiplas consultas. Alguns exemplos são:

  • Busca de região: Preprocesse um conjunto de pontos de modo a eficientemente contar os pontos dentro de uma região de consulta.
  • Localização de ponto: Dada uma partição do espaço em células, obtenha uma estrutura de dados que eficientemente diga em que região um ponto de consulta se encontra.
  • Vizinho mais próximo: Preprocesse um conjunto de pontos de modo a eficientemente determinar o ponto mais próximo de um ponto de consulta.
  • Traçado de raios: Dado um conjunto de objetos no espaço, produza uma estrutura de dados que eficientemente diga qual objeto que um raio de consulta intercepta primeiro.

Referências

  1. ↑ Franco P. Preparata and Michael Ian Shamos (1985). Computational Geometry - An Introduction. [S.l.]: Springer-Verlag. 1st edition: ISBN 0-387-96131-3; 2nd printing, corrected and expanded, 1988: ISBN 3-540-96131-3 

Ligações externas

Read other articles:

Hedvig Elisabet av Kurland

Hedvig Elisabet av Kurland. Hedvig Elisabeth von Biron av Kurland, född 23 juni 1727 i Mitau, död där 1797, var en rysk hovdam. Hon var hovmästarinna åt Elisabet av Ryssland och intog en framträdande plats vid det ryska hovet. Hon var dotter till hertig Ernst Johann von Biron av Kurland och Benigna Gottlieb von Trotha gt Treyden. Hon beskrivs som ful, med en missformad kropp med puckelrygg, men fick en fin utbildning under överinseende av kejsarinnan Anna Ivanovna. När hennes far utn�...

 

Mitsubishi J2M

Japanese land-based interceptor aircraft J2M Raiden Profile view of a Mitsubishi J2M Raiden Role Fighter aircraftType of aircraft Manufacturer Mitsubishi Heavy Industries First flight 20 March 1942 Introduction December 1942 Retired August 1945 Primary user Imperial Japanese Navy Number built 621 The Mitsubishi J2M Raiden (雷電, Lightning Bolt) is a single-engined land-based fighter aircraft used by the Imperial Japanese Navy Air Service in World War II. The Allied reporting name was J...

 

Файл:Off the Wall cover.jpg

Изображение было скопировано с wikipedia:ru. Оригинальное описание содержало: Опис обложка альбома Off the Wall Джерело http://www.michael-jackson-trader.com/store/albums-vinyl.html Час створення 1979 Автор зображення Michael Jackson Ліцензія див. нижче Ліцензування Ця робота є невільною — тобто, не відповідає виз�...

Словаччина на літніх Олімпійських іграх 2016

Словаччина на Олімпійських іграх Код МОК:SVK НОК:Національний олімпійськийкомітет Словаччини Олімпійські ігри в Ріо-де-Жанейро Спортсмени 51 у 12 видах спорту Прапороносець Данка Бартекова (відкриття)[1] Ерік Влчек (закриття) МедаліМісце: 37 Золото2 Срібло2 Брон

 

Льєрена

ЛьєренаLlerenaМуніципалітетКраїна  ІспаніяАвтономна спільнота ЕстремадураПровінція БадахосКоординати 38°14′17″ пн. ш. 6°00′54″ зх. д. / 38.238° пн. ш. 6.015° зх. д. / 38.238; -6.015Координати: 38°14′17″ пн. ш. 6°00′54″ зх. д. / 38.238° пн. �...

 

Cake (Amerikaanse band)

Cake Cake live op het Incuya Music Festival in 2018. Achtergrondinformatie Ook bekend als CAKE Jaren actief 1991 - heden Oorsprong Sacramento, CaliforniëVlag van Verenigde Staten Verenigde Staten Genre(s) Alternatieve rock, Indierock Label(s) Capricorn, Columbia, Upbeat Bezetting Huidige leden John McCreaVince DiFioreTodd RoperXan McCurdyDaniel McCallum Oud-leden Greg BrownFrank FrenchShon MeckfesselGabe NelsonVictor DamianiPete McNealPaulo BaldiCasey Lipka Officiël...

Вовненко Тетяна Олександрівна

Вовненко Тетяна ОлександрівнаНародилася 8 серпня 1957(1957-08-08) (66 років)село Липняжка, тепер Добровеличківського району Кіровоградської областіКраїна  СРСРНаціональність українкаДіяльність політична діячкаПартія КПРС У Вікіпедії є статті про інших людей із прізвищем �...

 

سامانثا روز

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

 

Buckley School (New York City)

Private independent school in New York City This article is about the school in Manhattan. For the school in Los Angeles, see Buckley School (California). The Buckley SchoolSchool crestAddress113 East 73rd StreetNew York City, New YorkUnited StatesCoordinates40°46′18.4″N 73°57′44.1″W / 40.771778°N 73.962250°W / 40.771778; -73.962250InformationTypePrivate IndependentMottoHonor et Veritas(Honor and truth)Established1913FounderB. Lord BuckleyHead of schoolGreg...

المقبرة الجلمودية

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

 

New Bedford, Massachusetts

New Bedford redirects here. For other uses, see New Bedford (disambiguation). Not to be confused with Bedford, Massachusetts. City in Massachusetts, United StatesNew Bedford, Massachusetts AccushnetCityNew Bedford Harbour SealWordmarkNickname: The Whaling CityMotto(s): Lucem Diffundo (Latin)I Diffuse Light[1]Location in Bristol County, MassachusettsNew BedfordLocation in MassachusettsShow map of MassachusettsNew BedfordLocation in the United StatesShow map of the United Stat...

 

九八式水上偵察機

九八式水上偵察機 九八式水上偵察機（きゅうはちしき すいじょう ていさつき）とは日本海軍が愛知航空機に開発させ、昭和13年（1938年）6月に兵器採用した飛行艇型の艦載夜間偵察機である。採用以前の旧名称は愛知十一試特種水上偵察機。略符号はE11A1[1]。連合軍コードネームは“Laura”。 水雷戦隊の夜戦における夜間触接、夜間砲戦における弾着観測など、敵...

العلاقات البليزية النيجيرية

العلاقات البليزية النيجيرية بليز نيجيريا   بليز   نيجيريا تعديل مصدري - تعديل   العلاقات البليزية النيجيرية هي العلاقات الثنائية التي تجمع بين بليز ونيجيريا.[1][2][3][4][5] مقارنة بين البلدين هذه مقارنة عامة ومرجعية للدولتين: وجه المقارنة بليز �...

 

الحظر

الملكى المحظور 1651، من رسم جون إيفرت ميليه في عام 1853، والتي فيها تختبئ امرأة من البيوريتانين ومهاجرًا ملكيًا فارًا في جوف شجرة الحظر (باللاتينية: proscriptio)‏، في الاستخدام الحالي، هو مرسوم الإدانة بالموت أو الإبعاد، ويمكن استخدامه في سياق سياسي للإشارة إلى القتل أو الإبعاد من ...

 

Islamic honorifics

Laudatory religious phrases in Islam Peace be upon him redirects here. For the Jewish honorific, see Honorifics for the dead in Judaism § Peace be upon him/her. This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Islamic honorifics – news · newspapers · books · scholar · JSTOR (April 2022) (Learn how and w...

Mirza Shirazi

Iraqi-Iranian Shia marja' (1815–1895) For other people with the same name, see Shirazi. Grand Ayatollah Mujaddid MirzaMuhammad-Hassan al-Shiraziالميرزا محمد حسن الحسيني الشيرازيTitleGrand Ayatollah MujaddidPersonalBornApril 25, 1815Shiraz, Qajar IranDiedFebruary 20, 1895(1895-02-20) (aged 79)Samarra, Ottoman IraqResting placeImam Ali ShrineReligionIslamChildrenMuhammadAli AghaJurisprudenceTwelver ShiaOther namesal-Mirza al-Kabir, Arabic: الميرزا...

 

Kingdom of Serbia

This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Kingdom of Serbia – news · newspapers · books · scholar · JSTOR (October 2023) (Learn how and when to remove this template message)1882–1918 country in Southeast Europe For other uses, see Kingdom of Serbia (disambiguation). Kingdom of SerbiaКраљевин�...

 

Caribbean Clipper

1943 song by The Glenn Miller OrchestraCaribbean ClipperSong by The Glenn Miller OrchestraA-sideBlue RainReleased1943GenreBig band, jump bluesLength2:45[1]LabelVictorComposer(s)Jerry GrayLyricist(s)Sammy Gallop Caribbean Clipper is a big band and jump song recorded by Glenn Miller and his Orchestra in 1942. The song was composed by Jerry Gray with lyrics by Sammy Gallop.[1] The song was part of a number of songs—including Sun Valley Jump, Here We Go Again, The Spirit Is Will...

Surakshaa (1995 film)

1995 Indian filmSurakshaaRelease posterDirected byRaju MavaniWritten byTaluk DaarsProduced byRaju MavaniStarringAditya PancholiSunil ShettySaif Ali KhanMonica BediDivya DuttaSheebaCinematographySanjay MalvankarEdited byA. MuthuMusic byAnu MalikRelease date 3 March 1995 (1995-03-03) Running time148 minsCountryIndiaLanguageHindi Surakshaa is a 1995 Indian Hindi-language action comedy film directed and produced by Raju Mavani. It stars Aditya Pancholi, Sunil Shetty, Saif Ali Khan,...

 

Servant (TV series)

American psychological horror television series (2019–2023) ServantGenre Drama Psychological horror Thriller Created byTony BasgallopStarring Lauren Ambrose Toby Kebbell Nell Tiger Free Rupert Grint ComposerTrevor GureckisCountry of originUnited StatesOriginal languageEnglishNo. of seasons4No. of episodes40ProductionExecutive producers Tony Basgallop M. Night Shyamalan Ashwin Rajan Jason Blumenthal Todd Black Steve Tisch Production locationPhiladelphia, PennsylvaniaCinematography Mike Gioul...

 
Kembali kehalaman sebelumnya