NDLI: Minimum-cost coverage of point sets by disks

Please wait, while we are loading the content...

Minimum weight triangulation is NP-hard

Conflict-free colorings of shallow discs

Locked and unlocked chains of planar shapes

Ray shooting and intersection searching amidst fat convex polyhedra in 3-space

Topology guaranteeing manifold reconstruction using distance function to noisy data

Simple and semi-dynamic structures for cache-oblivious planar orthogonal range searching

Complete subdivision algorithms, I: intersection of Bezier curves

The density of iterated crossing points and a gap result for triangulations of finite point sets

A sampling theory for compact sets in Euclidean space

Improved output-sensitive snap rounding

On overlays and minimization diagrams

Splitting (complicated) surfaces is hard

Minimum-cost coverage of point sets by disks

Geometry-based reasoning for a large sensor network

Discrete differential forms and applications to surface tiling

The effect of corners on the complexity of approximate range searching

How to play a coloring game against a color-blind adversary

Refolding planar polygons

On the ICP algorithm

Vines and vineyards by updating persistence in linear time

I/O-efficient batched union-find and its applications to terrain analysis

The predicates for the Voronoi diagram of ellipses

Random triangulations of planar point sets

Medial axis approximation and unstable flow complex

Iterated snap rounding with bounded drift

How to get close to the median shape

Computing shortest non-trivial cycles on orientable surfaces of bounded genus in almost linear time

Algorithms for two-box covering

Projective clustering and its application to surface reconstruction: extended abstract

Efficient algorithm for approximating maximum inscribed sphere in high dimensional polytope

Colored intersection searching via sparse rectangular matrix multiplication

Computing the Fréchet distance between simple polygons in polynomial time

An upper bound on the average size of silhouettes

Persistence-sensitive simplification functions on 2-manifolds

On realistic terrains

An approximate arrangement algorithm for semi-algebraic curves

Pre-triangulations and liftable complexes

Provably good sampling and meshing of Lipschitz surfaces

Hole detection or: "how much geometry hides in connectivity?"

Envelope surfaces

Tight bounds for connecting sites across barriers

Exact computation of protein structure similarity

A portable geometric algorithm visualization system with dynamic camera positioning for tracking 3D objects

An optimal-time algorithm for shortest paths on a convex polytope in three dimensions

A fast k-means implementation using coresets

Embedding ultrametrics into low-dimensional spaces

The orienteering problem in the plane revisited

Engineering a compact parallel delaunay algorithm in 3D

Sliver removal by lattice refinement

Online geometric reconstruction

Illustrating the streaming construction of 2D delaunay triangulations

How slow is the k-means method?

Plane embeddings of planar graph metrics

Degenerate crossing numbers

Minimum-cost load-balancing partitions

Approximating minimum-cost polygonal paths of bounded number of links in weighted subdivisions

Lower bounds on locality sensitive hashing

Volume distortion for subsets of Euclidean spaces: extended abstract

On the maximum number of edges in topological graphs with no four pairwise crossing edges

Optimal succinct representations of planar maps

On approximating the smallest enclosing Bregman Balls

Minimum-cost coverage of point sets by disks

Content Provider	ACM Digital Library
Author	Mitchell, Joseph S. B. Knauer, Christian Whittlesey, Kim Brönnimann, Hervé Arkin, Esther M. Erickson, Jeff Fekete, Sándor P. Alt, Helmut Lenchner, Jonathan
Abstract	We consider a class of geometric facility location problems in which the goal is to determine a set X of disks given by their centers $(t_{j})$ and radii $(r_{j})$ that cover a given set of demand points $Y∈R^{2}$ at the smallest possible cost. We consider cost functions of the form $Ε_{j}f(r_{j}),$ where $f(r)=r^{α}$ is the cost of transmission to radius r. Special cases arise for α=1 (sum of radii) and α=2 (total area); power consumption models in wireless network design often use an exponent α>2. Different scenarios arise according to possible restrictions on the transmission centers $t_{j},$ which may be constrained to belong to a given discrete set or to lie on a line, etc.We obtain several new results, including (a) exact and approximation algorithms for selecting transmission points $t_{j}$ on a given line in order to cover demand points $Y∈R^{2};$ (b) approximation algorithms (and an algebraic intractability result) for selecting an optimal line on which to place transmission points to cover Y; (c) a proof of NP-hardness for a discrete set of transmission points in $R^{2}$ and any fixed α>1; and (d) a polynomial-time approximation scheme for the problem of computing a minimum cost covering tour (MCCT), in which the total cost is a linear combination of the transmission cost for the set of disks and the length of a tour/path that connects the centers of the disks.
Starting Page	449
Ending Page	458
Page Count	10
File Format	PDF
ISBN	1595933409
DOI	10.1145/1137856.1137922
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2006-06-05
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Covering problems Approximation Geometric optimization Tour problems Complexity
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in