東華大學圖書館 |

Language: English

Help

回圖書館首頁

手機版館藏查詢

Back

Switch To: Labeled | MARC Mode | ISBD

Proximity problems in two and three ...

Bitner, Steven Philippe.

Linked to FindBook

Google Book

Amazon

博客來

Proximity problems in two and three dimensional Euclidean space .

Record Type:	Language materials, printed : Monograph/item
Title/Author:	Proximity problems in two and three dimensional Euclidean space ./
Author:	Bitner, Steven Philippe.
Description:	122 p.
Notes:	Source: Dissertation Abstracts International, Volume: 71-10, Section: B, page: 6217.
Contained By:	Dissertation Abstracts International71-10B.
Subject:	Applied Mathematics. -
Online resource:	http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=3421494
ISBN:	9781124206691

Proximity problems in two and three dimensional Euclidean space .
Bitner, Steven Philippe.

Proximity problems in two and three dimensional Euclidean space . - 122 p.

Source: Dissertation Abstracts International, Volume: 71-10, Section: B, page: 6217.

Thesis (Ph.D.)--The University of Texas at Dallas, 2010.

In this dissertation we consider three problems in computational geometry. We begin with an overview of computational geometry and some background knowledge. We discuss several important data structures as well as briefly summarize the known results for finding the data structures discussed. Next, we give a solution for the farthest line segment problem. Given a set S of n points in R3 , we give an algorithm which will return the farthest line segment spanned by S from an input query point in O( n log n) time. This time is optimal in the algebraic decision tree model.

ISBN: 9781124206691Subjects--Topical Terms:

1669109
Applied Mathematics.

Proximity problems in two and three dimensional Euclidean space .
LDR:02906nam 2200313 4500 001 1395993
005 20110527105442.5
008 130515s2010 ||||||||||||||||| ||eng d
020 $a 9781124206691
035 $a (UMI)AAI3421494
035 $a AAI3421494
040 $a UMI $c UMI
100 1 $a Bitner, Steven Philippe. $3 1674741
245 1 0 $a Proximity problems in two and three dimensional Euclidean space .
300 $a 122 p.
500 $a Source: Dissertation Abstracts International, Volume: 71-10, Section: B, page: 6217.
500 $a Adviser: Ouidiu Daescu.
502 $a Thesis (Ph.D.)--The University of Texas at Dallas, 2010.
520 $a In this dissertation we consider three problems in computational geometry. We begin with an overview of computational geometry and some background knowledge. We discuss several important data structures as well as briefly summarize the known results for finding the data structures discussed. Next, we give a solution for the farthest line segment problem. Given a set S of n points in R3 , we give an algorithm which will return the farthest line segment spanned by S from an input query point in O( n log n) time. This time is optimal in the algebraic decision tree model.
520 $a Then we address the minimum sum dipolar spanning tree (MSST) problem in R3 . This problem seeks to find two congruent balls centered at two points in the input set S such that the sum of the distance between their centers and the radius of the balls is minimized. These balls must cover the set S to be valid solutions. We give an O( n2 log2 n) time and O(n2) space algorithm which adds only a logarithmic factor to the two dimensional version. Our algorithm can also return a solution to the discrete 2-center problem without an addition to the asymptotic running time. This running time outperforms the speed of the best known algorithm for the continuous 2-center problem in R3 .
520 $a Finally, we give solutions to a new problem which we refer to as the bichromatic circular separation problem. Given two sets of points in R2 , one red and one blue, the problem is to find the minimum size circle such that all red points are in the interior of the circle and as few blue points as possible lie inside the same circle. We offer three solutions, two of which run in O(nm log m + n log n) time and use linear space. The third algorithm runs in O*(m 1.5) + O(m log n) time and uses O(n) + O(m1.5) space. The O*() notation ignores a polylogarithmic factor.
520 $a We conclude with a look at our ongoing work and some partial results that have been motivated by the work contained in this dissertation.
590 $a School code: 0382.
650 4 $a Applied Mathematics. $3 1669109
650 4 $a Computer Science. $3 626642
690 $a 0364
690 $a 0984
710 2 $a The University of Texas at Dallas. $3 1018411
773 0 $t Dissertation Abstracts International $g 71-10B.
790 1 0 $a Daescu, Ouidiu, $e advisor
790 $a 0382
791 $a Ph.D.
792 $a 2010
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=3421494