Desain Algoritma Query Dinamis Berbasis Struktur Data Segment Tree Dengan Metode Divide And Conquer Pada Permasalahan Geometri Komputasional: Studi Kasus SPOJ 5902 Tri

Yohanes, Emmanuel Maximus (2022) Desain Algoritma Query Dinamis Berbasis Struktur Data Segment Tree Dengan Metode Divide And Conquer Pada Permasalahan Geometri Komputasional: Studi Kasus SPOJ 5902 Tri. Undergraduate thesis, Institut Teknologi Sepuluh Nopember.

Text 05111840000102-Undergraduate_Thesis.pdf - Accepted Version Restricted to Repository staff only until 1 April 2024. Download (1MB) | Request a copy

Abstract

Terdapat K buah titik berbeda yang terletak pada ruang koordinat dua dimensi. Diberikan juga M pasang titik berbeda yang terletak dalam ruang koordinat tersebut, di mana setiap pasang titik dapat membentuk sebuah segitiga dengan titik (0, 0). Persoalan yang ingin diselesaikan pada Tugas Akhir ini adalah menentukan apakah pada masing-masing dari M segitiga terdapat paling tidak satu titik dari K yang berada di dalam segitiga tersebut. Permasalahan ini disederhanakan dalam bentuk soal yang dapat diakses pada halaman SPOJ 5902 Tri.
Dikarenakan kasus persoalan berupa rentang yang dapat berubah, diperlukan sebuah metode query dinamis yang diimplementasikan dalam bentuk struktur data segment tree, sehingga operasi query rentang dapat dilakukan dengan kompleksitas waktu logaritmik. Pada setiap rentang dalam segment tree, mencari keberadaan titik yang memenuhi kriteria persoalan dapat dioptimasi dengan penggunaan binary search dengan mempergunakan properti spesial convex hull. Maka, pada setiap segmen perlu dibuat sebuah convex hull dari titik-titik yang memenuhi segmen tersebut.
================================================================================================
Consider K different points in a two-dimensional coordinate space, and M pairs of points in the same coordinate space, where each pair forms the corners of a triangle with the third corner positioned at the origin (0, 0). This thesis aims to solve the problem of computing whether each triangle of the M triangles contains at least one point of K points. This problem is an abstraction of the full problem which can be accessed at the SPOJ 5902 Tri problem website.
Due to the nature of the problem where the ranges are changing with each query, it is required to devise a dynamic query method, which is implemented as a segment tree data structure that can compute range operations under logarithmic time complexity. On each segment tree range, testing the existence of a point that fulfills the problem criteria can be optimized by the use of binary search, which is possible due to the properties of convex hulls. Thus, a convex hull of points in the segment is built for each segment in the problem range.

Item Type:	Thesis (Undergraduate)
Uncontrolled Keywords:	binary search, convex hull, query dinamis, segment tree, dynamic query
Subjects:	Q Science > QA Mathematics > QA76.F56 Data structures (Computer science) Q Science > QA Mathematics > QA9.58 Algorithms
Divisions:	Faculty of Intelligent Electrical and Informatics Technology (ELECTICS) > Informatics Engineering > 55201-(S1) Undergraduate Thesis
Depositing User:	Emmanuel Maximus Yohanes
Date Deposited:	27 Jan 2022 05:52
Last Modified:	27 Jan 2022 05:52
URI:	http://repository.its.ac.id/id/eprint/92521

Actions (login required)

View Item