Advanced search options

Advanced Search Options 🞨

Browse by author name (“Author name starts with…”).

Find ETDs with:

in
/  
in
/  
in
/  
in

Written in Published in Earliest date Latest date

Sorted by

Results per page:

Sorted by: relevance · author · university · dateNew search

You searched for subject:(Disk Packing). Showing records 1 – 3 of 3 total matches.

Search Limiters

Last 2 Years | English Only

No search limiters apply to these results.

▼ Search Limiters


University of Illinois – Chicago

1. Mohajer, Ali. Upper Bounds on the Density of Two Radius Packings of Disks in the Plane.

Degree: 2018, University of Illinois – Chicago

A new upper density bound on two-radius packings of disks in the plane is presented at a homogeneity which does not admit compact packings. Advisors/Committee Members: Shalen, Peter B (advisor), Culler, Marc (committee member), Dumas, David (committee member), Groves, Daniel (committee member), Takloo-Bighash, Ramin (committee member), Kennedy, Thomas G (committee member), Shalen, Peter B (chair).

Subjects/Keywords: Packing; Disk Packing; Disk Packing in the Plane; Two-radius Packing; Packing Density; Binary Packing; Upper Density Bound; Delaunay Triangulation; Surfeit; Adjusted Surfeit; Saturated Packing

Record DetailsSimilar RecordsGoogle PlusoneFacebookTwitterCiteULikeMendeleyreddit

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6th Edition):

Mohajer, A. (2018). Upper Bounds on the Density of Two Radius Packings of Disks in the Plane. (Thesis). University of Illinois – Chicago. Retrieved from http://hdl.handle.net/10027/23245

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16th Edition):

Mohajer, Ali. “Upper Bounds on the Density of Two Radius Packings of Disks in the Plane.” 2018. Thesis, University of Illinois – Chicago. Accessed July 10, 2020. http://hdl.handle.net/10027/23245.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7th Edition):

Mohajer, Ali. “Upper Bounds on the Density of Two Radius Packings of Disks in the Plane.” 2018. Web. 10 Jul 2020.

Vancouver:

Mohajer A. Upper Bounds on the Density of Two Radius Packings of Disks in the Plane. [Internet] [Thesis]. University of Illinois – Chicago; 2018. [cited 2020 Jul 10]. Available from: http://hdl.handle.net/10027/23245.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Mohajer A. Upper Bounds on the Density of Two Radius Packings of Disks in the Plane. [Thesis]. University of Illinois – Chicago; 2018. Available from: http://hdl.handle.net/10027/23245

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation


University of Waterloo

2. Lafreniere, Benjamin J. Packing Unit Disks.

Degree: 2008, University of Waterloo

Given a set of unit disks in the plane with union area A, what fraction of A can be covered by selecting a pairwise disjoint subset of the disks? Richard Rado conjectured 1/4 and proved 1/4.41. In this thesis, we consider a variant of this problem where the disjointness constraint is relaxed: selected disks must be k-colourable with disks of the same colour pairwise-disjoint. Rado's problem is then the case where k = 1, and we focus our investigations on what can be proven for k > 1. Motivated by the problem of channel-assignment for Wi-Fi wireless access points, in which the use of 3 or fewer channels is a standard practice, we show that for k = 3 we can cover at least 1/2.09 and for k = 2 we can cover at least 1/2.82. We present a randomized algorithm to select and colour a subset of n disks to achieve these bounds in O(n) expected time. To achieve the weaker bounds of 1/2.77 for k = 3 and 1/3.37 for k = 2 we present a deterministic O(n2) time algorithm. We also look at what bounds can be proven for arbitrary k, presenting two different methods of deriving bounds for any given k and comparing their performance. One of our methods is an extension of the method used to prove bounds for k = 2 and k = 3 above, while the other method takes a novel approach. Rado's proof is constructive, and uses a regular lattice positioned over the given set of disks to guide disk selection. Our proofs are also constructive and extend this idea: we use a k-coloured regular lattice to guide both disk selection and colouring. The complexity of implementing many of the constructions used in our proofs is dominated by a lattice positioning step. As such, we discuss the algorithmic issues involved in positioning lattices as required by each of our proofs. In particular, we show that a required lattice positioning step used in the deterministic O(n2) algorithm mentioned above is 3SUM-hard, providing evidence that this algorithm is optimal among algorithms employing such a lattice positioning approach. We also present evidence that a similar lattice positioning step used in the constructions for our better bounds for k = 2 and k = 3 may not have an efficient exact implementation.

Subjects/Keywords: computational geometry; disk packing; covering; colouring; maximum independent set; lower bounds; discrete geometry; algorithms; complexity; disk intersection graphs

Record DetailsSimilar RecordsGoogle PlusoneFacebookTwitterCiteULikeMendeleyreddit

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6th Edition):

Lafreniere, B. J. (2008). Packing Unit Disks. (Thesis). University of Waterloo. Retrieved from http://hdl.handle.net/10012/3907

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16th Edition):

Lafreniere, Benjamin J. “Packing Unit Disks.” 2008. Thesis, University of Waterloo. Accessed July 10, 2020. http://hdl.handle.net/10012/3907.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7th Edition):

Lafreniere, Benjamin J. “Packing Unit Disks.” 2008. Web. 10 Jul 2020.

Vancouver:

Lafreniere BJ. Packing Unit Disks. [Internet] [Thesis]. University of Waterloo; 2008. [cited 2020 Jul 10]. Available from: http://hdl.handle.net/10012/3907.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Lafreniere BJ. Packing Unit Disks. [Thesis]. University of Waterloo; 2008. Available from: http://hdl.handle.net/10012/3907

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

3. Hu, Nan. Approximation Algorithms for Geometric Covering Problems for Disks and Squares.

Degree: 2013, University of Waterloo

Geometric covering is a well-studied topic in computational geometry. We study three covering problems: Disjoint Unit-Disk Cover, Depth-(≤ K) Packing and Red-Blue Unit-Square Cover. In the Disjoint Unit-Disk Cover problem, we are given a point set and want to cover the maximum number of points using disjoint unit disks. We prove that the problem is NP-complete and give a polynomial-time approximation scheme (PTAS) for it. In Depth-(≤ K) Packing for Arbitrary-Size Disks/Squares, we are given a set of arbitrary-size disks/squares, and want to find a subset with depth at most K and maximizing the total area. We prove a depth reduction theorem and present a PTAS. In Red-Blue Unit-Square Cover, we are given a red point set, a blue point set and a set of unit squares, and want to find a subset of unit squares to cover all the blue points and the minimum number of red points. We prove that the problem is NP-hard, and give a PTAS for it. A "mod-one" trick we introduce can be applied to several other covering problems on unit squares.

Subjects/Keywords: computational geometry; approximation algorithm; PTAS; Red-Blue Set Cover; Depth-(<; K) Packing; Disjoint Unit-Disk Cover

…in this dissertation: 1. Disjoint Unit-Disk Cover, 4 2. Depth-≤ K Packing for Arbitrary… …x5D; for k-Coloured Disk Packing. Given a set A of unit disks and k colours where k ∈ {… …the objects. For example, in the Unit-Disk Cover problem, given a point set, one wants to… …geometric objects, and wants to find the optimal subset. The discrete version of the Unit-Disk… …such as the Unit-Disk Cover problem. Mustafa and Ray [31] gave the first PTAS for… 

Record DetailsSimilar RecordsGoogle PlusoneFacebookTwitterCiteULikeMendeleyreddit

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6th Edition):

Hu, N. (2013). Approximation Algorithms for Geometric Covering Problems for Disks and Squares. (Thesis). University of Waterloo. Retrieved from http://hdl.handle.net/10012/7703

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16th Edition):

Hu, Nan. “Approximation Algorithms for Geometric Covering Problems for Disks and Squares.” 2013. Thesis, University of Waterloo. Accessed July 10, 2020. http://hdl.handle.net/10012/7703.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7th Edition):

Hu, Nan. “Approximation Algorithms for Geometric Covering Problems for Disks and Squares.” 2013. Web. 10 Jul 2020.

Vancouver:

Hu N. Approximation Algorithms for Geometric Covering Problems for Disks and Squares. [Internet] [Thesis]. University of Waterloo; 2013. [cited 2020 Jul 10]. Available from: http://hdl.handle.net/10012/7703.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Hu N. Approximation Algorithms for Geometric Covering Problems for Disks and Squares. [Thesis]. University of Waterloo; 2013. Available from: http://hdl.handle.net/10012/7703

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

.