NDLI: Computing Maximally Separated Sets in the Plane

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Agarwal, Pankaj K. Sharir, Micha Overmars, Mark
Copyright Year	2006
Abstract	Let S be a set of n points in $\reals^2$. Given an integer $1 \le k \le n$, we wish to find a maximally separated subset $I \subseteq S$ of size k; this is a subset for which the minimum among the ${k\choose 2}$ pairwise distances between its points is as large as possible. The decision problem associated with this problem is to determine whether there exists $I\subseteq S$, $\|I\|=k$, so that all ${k\choose 2}$ pairwise distances in I are at least 2. This problem can also be formulated in terms of diskintersection graphs: Let D be the set of unit disks centered at the points of S. The diskintersection graph G of D has as edges all pairs of disks with nonempty intersection. Any set I with the above properties is then the set of centers of disks that form an independent set in the graph G. This problem is known to be NPcomplete if k is part of the input. In this paper we first present a lineartime $\eps$approximation algorithm for any constant k. Next we give exact algorithms for the cases $k=3$ and $k=4$ that run in time $O(n^{4/3}\polylog(n))$. We also present a simpler $n^{O(\sqrt{k})}$time exact algorithm as compared with the recent algorithm in J. Alber and J. Fiala, J. Algorithms, 52 2004, pp. 134151 for arbitrary values of k.
Starting Page	815
Ending Page	834
Page Count	20
File Format	PDF
ISSN	00975397
DOI	10.1137/S0097539704446591
e-ISSN	10957111
Journal	SIAM Journal on Computing (SMJCAT)
Issue Number	3
Volume Number	36
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2006-11-03
Access Restriction	Subscribed
Subject Keyword	Analysis of algorithms and problem complexity Computer graphics; computational geometry Approximation algorithms geometric optimization diskintersection graphs independent set
Content Type	Text
Resource Type	Article
Subject	Mathematics Computer Science

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

Computing Maximally Separated Sets in the Plane (2006)

Improving the Stretch Factor of a Geometric Network by Edge Augmentation

Computing Maximum Independent Set on Outerstring Graphs and Their Relatives

Shortest Paths Help Solve Geometric Optimization Problems in Planar Regions

A note on maximum independent sets and minimum clique partitions in unit disk graphs and penny graphs: complexity and approximation

A Constant-Factor Approximation Algorithm for the Geometric k-MST Problem in the Plane

Computing the Homology of Semialgebraic Sets I: Lax Formulas

Computing the Homology of Semialgebraic Sets. II: General formulas

An Optimal Algorithm for Computing Visibility in the Plane

Computing Maximally Separated Sets in the Plane

Similar Documents

Computing Maximally Separated Sets in the Plane (2006)

Improving the Stretch Factor of a Geometric Network by Edge Augmentation

Computing Maximum Independent Set on Outerstring Graphs and Their Relatives

Shortest Paths Help Solve Geometric Optimization Problems in Planar Regions

A note on maximum independent sets and minimum clique partitions in unit disk graphs and penny graphs: complexity and approximation

A Constant-Factor Approximation Algorithm for the Geometric k-MST Problem in the Plane

Computing the Homology of Semialgebraic Sets I: Lax Formulas

Computing the Homology of Semialgebraic Sets. II: General formulas

An Optimal Algorithm for Computing Visibility in the Plane

Computing Maximally Separated Sets in the Plane