Subject » BMEVISZD304
Algorithms in Geometry
Geometriai algoritmusok
A tantárgyleírás hatályossága
Hatályosság kezdete:
2026. March 21.
Hatályosság vége:
—
| Subject name (Hungarian, English) |
Geometriai algoritmusok
Algorithms in Geometry
|
||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Subject code | BMEVISZD304 | ||||||||||||
| Subject type | — | ||||||||||||
| Training Level | — | ||||||||||||
| Course types and hours (weekly/semester) |
|
||||||||||||
| Assessment type | vizsga | ||||||||||||
| Credits | 3 | ||||||||||||
| Subject coordinator |
Tóth Géza
position: egyetemi docens
contact:
toth.geza@vik.bme.hu
|
||||||||||||
| Responsible department |
Számítástudományi és Információelméleti Tanszék
|
||||||||||||
| Faculty | Villamosmérnöki és Informatikai Kar | ||||||||||||
| Subject website | www.vik.bme.hu | ||||||||||||
| Primary curriculum type | — | ||||||||||||
| Direct prerequisites – Strong prerequisite | none | ||||||||||||
| Direct prerequisites – Weak prerequisite | none | ||||||||||||
| Direct prerequisites – Parallel prerequisite | none | ||||||||||||
| Direct prerequisites – Milestone prerequisite | none | ||||||||||||
| Direct prerequisites – Exclusion | none |
Objectives
Programme
Computation of convex hull in the plane, degenerate cases, robustness.
Segment intersection, computing the overlay of two maps.
Polygon triangulation, its computation, the art gallery problem.
Linear programming in low dimensions, incremental and randomized.
Smallest enclosing disc.
Range searching, range trees.
Point location, trapezoidal maps. Randomized incremental approach.
Voronoi diagrams, properties and computation.
Arrangements of lines, point-line duality, levels in an arrangement,
discrepancy.
Triangulations of point sets, Delaunay triangulations, properties,
relationship with the Voronoi diagram, computation.
Computing the convex hull in the space.
The k-set problem, bounds and applications.
Crossing numbers of graphs, results, bounds, related problems.
Segment intersection, computing the overlay of two maps.
Polygon triangulation, its computation, the art gallery problem.
Linear programming in low dimensions, incremental and randomized.
Smallest enclosing disc.
Range searching, range trees.
Point location, trapezoidal maps. Randomized incremental approach.
Voronoi diagrams, properties and computation.
Arrangements of lines, point-line duality, levels in an arrangement,
discrepancy.
Triangulations of point sets, Delaunay triangulations, properties,
relationship with the Voronoi diagram, computation.
Computing the convex hull in the space.
The k-set problem, bounds and applications.
Crossing numbers of graphs, results, bounds, related problems.
The course presents the fundamental problems,
concepts, and methods in computational geometry.
Learning outcomes
Ez a tantárgy a KKK rendeletben meghatározott, következő kompetenciák fejlesztését szolgálja:
Knowledge
No learning outcomes recorded.
Skills
No learning outcomes recorded.
Attitudes
No learning outcomes recorded.
Autonomy and responsibility
No learning outcomes recorded.
Oktatási módszertan
Lecture
Tanulástámogató anyagok
Online források
Mark de Berg, Otfried Cheong (Schwarzkopf), Marc van Kreveld, Mark Overmars:; Computational Geometry: Algorithms and Applications, Springer, 2008.
Recommended preliminary knowledge for completing the subject
Knowledge type competencies
(azon előzetes ismeretek összessége, amelyek megléte nem kötelező, de a tantárgy eredményes teljesítését nagyban elősegíti)
Basic knowledge of linear algebra, graph theory, theory of algorithms
is required.
Skill type competencies
(azon előzetes képességek és készségek összessége, amelyek megléte nem kötelező, de a tantárgy eredményes teljesítését nagyban elősegíti)
nincs
Recommended (non-compulsory) preliminary competencies
(azon ajánlott (nem kötelező) előzetesen megszerzendő kompetenciák összessége, amelyek jelentősen hozzájárulnak a tantárgy eredményes teljesítéséhez)
Basic knowledge of linear algebra, graph theory, theory of algorithms
is required.
General rules
Requirements:
Exam
Additional possibilities:
Additional exam(s) according to the rules of the University
Assessment methods
In-term assessments
No detailed assessments provided.
Weight of in-term assessments
No weights provided.
Exam-period assessments
No detailed assessments provided.
Weight of exam elements
No weights provided.
Grade calculation
No grade thresholds provided.
Attendance requirements
No attendance requirements provided.
Rules for retake and resubmission
Not provided.
Short description
Not provided.
Detailed description
Not provided.
Recommended courses
Not provided.
Workload to complete the subject
No workload breakdown provided.
Validity of subject requirements
Requirements valid from:
—
Requirements valid until:
—
Curriculum placement
No curriculum placements recorded for this subject version.