DC Field | Value | Language |
---|---|---|
dc.contributor.advisor | Cheong, Otfried | - |
dc.contributor.advisor | 정지원 | - |
dc.contributor.author | Shin, Min-Ho | - |
dc.contributor.author | 신민호 | - |
dc.date.accessioned | 2015-04-23T06:16:11Z | - |
dc.date.available | 2015-04-23T06:16:11Z | - |
dc.date.issued | 2013 | - |
dc.identifier.uri | http://library.kaist.ac.kr/search/detail/view.do?bibCtrlNo=567065&flag=dissertation | - |
dc.identifier.uri | http://hdl.handle.net/10203/196868 | - |
dc.description | 학위논문(석사) - 한국과학기술원 : 전산학과, 2013.8, [ iii, 27 p. ] | - |
dc.description.abstract | Given a set of $n$ black points $B$ in the plane, we want to place a set of red points $R$ so that every point in $B$ is a neighbor of at least one point in $R$ on the Delaunay triangulation of $B \cup R$. We give the following bounds. For the lower bound, we construct a set of $n$ black points so that we need at least $\frac{n}{4}$ red points. For the upper bound, we introduce an algorithm that covers all $n$ black points using at most $\frac{n}{2}$ red points, which improves the previous upper bound of $\frac{2n}{3}$. We also provide algorithms that use at most \frac{n}{3}$ red points, under two different constraints. | eng |
dc.language | eng | - |
dc.publisher | 한국과학기술원 | - |
dc.subject | Delaunay triangulation | - |
dc.subject | 완전 정합 | - |
dc.subject | 분리 삼각형 | - |
dc.subject | 해밀턴 경로 | - |
dc.subject | 커버링 | - |
dc.subject | Delaunay 삼각 분할 | - |
dc.subject | Covering | - |
dc.subject | Hamiltonian Path | - |
dc.subject | Separating Triangle | - |
dc.subject | Perfect Matching | - |
dc.title | Covering delaunay triangulation | - |
dc.title.alternative | Delaunay 삼각 분할 커버링 | - |
dc.type | Thesis(Master) | - |
dc.identifier.CNRN | 567065/325007 | - |
dc.description.department | 한국과학기술원 : 전산학과, | - |
dc.identifier.uid | 020113315 | - |
dc.contributor.localauthor | Cheong, Otfried | - |
dc.contributor.localauthor | 정지원 | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.