Advanced search options

Sorted by: relevance · author · university · date | New search

You searched for `subject:(Disk Packing)`

.
Showing records 1 – 3 of
3 total matches.

▼ 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

URL: http://hdl.handle.net/10027/23245

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 Details Similar Records

❌

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

APA (6^{th} 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 (16^{th} 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 (7^{th} 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

Not specified: Masters Thesis or Doctoral Dissertation

University of Waterloo

2.
Lafreniere, Benjamin J.
* Packing* Unit Disks.

Degree: 2008, University of Waterloo

URL: http://hdl.handle.net/10012/3907

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(n^{2}) 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(n^{2}) 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 Details Similar Records

❌

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

APA (6^{th} Edition):

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

Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16^{th} Edition):

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

Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7^{th} 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.

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

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

URL: http://hdl.handle.net/10012/7703

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 Details Similar Records

❌

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

APA (6^{th} 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

Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16^{th} 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.

Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7^{th} 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.

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

Not specified: Masters Thesis or Doctoral Dissertation