MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Mustafa, Nabil H.
Ray, Saurabh
dblp
dblp
Not MPG Author(s):
Ray, Saurabh
Editor(s):
BibTeX cite key*:
NaRa07
Title, Booktitle
Title*:
An Optimal Generalization of the Centerpoint Theorem, and its Extensions
Booktitle*:
Proceedings of the Twenty-Third Annual Symposium on Computational Geometry (SCG'07)
Event, URLs
Conference URL::
http://www.socg.org/2007/
Downloading URL:
Event Address*:
Gyeongju, South Korea
Language:
English
Event Date*
(no longer used):
Organization:
Association for Computing Machinery (ACM)
Event Start Date:
6 June 2007
Event End Date:
8 June 2007
Publisher
Name*:
ACM
URL:
http://www.acm.org/
Address*:
New York, NY, USA
Type:
Vol, No, Year, pp.
Series:
Volume:
Number:
Month:
Pages:
138-141
Year*:
2007
VG Wort Pages:
ISBN/ISSN:
978-1-59593-705-6
Sequence Number:
DOI:
10.1145/1247069.1247097
Note, Abstract, ©
(LaTeX) Abstract:
We prove an optimal generalization of the centerpoint theorem: given a set P of n points in the plane, there exist two points (not necessarily among input points) that hit all convex objects containing more than 4n/7 points of P. We further prove that this bound is tight. We get this bound as part of a more general procedure for finding small number of points hitting convex sets over P, yielding several improvements over previous results.
URL for the Abstract:
http://doi.acm.org/10.1145/1247069.1247097

http://portal.acm.org/citation.cfm?id=1247069.1247097&coll=GUIDE&dl=GUIDE&type=series&idx=1247069&part=Proceedings&WantType=Proceedings&title=Annual%20Symposium%20on%20Computational%20Geometry&CFID=22430507&CFTOKEN=31336734
Download
Access Level:
Internal

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{NaRa07,
AUTHOR = {Mustafa, Nabil H. and Ray, Saurabh},
TITLE = {An Optimal Generalization of the Centerpoint Theorem, and its Extensions},
BOOKTITLE = {Proceedings of the Twenty-Third Annual Symposium on Computational Geometry (SCG'07)},
PUBLISHER = {ACM},
YEAR = {2007},
ORGANIZATION = {Association for Computing Machinery (ACM)},
PAGES = {138--141},
ADDRESS = {Gyeongju, South Korea},
ISBN = {978-1-59593-705-6},
DOI = {10.1145/1247069.1247097},
}


Entry last modified by Uwe Brahm, 02/28/2008
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Stefan Funke
Created
03/20/2007 02:08:42 PM
Revisions
4.
3.
2.
1.
0.
Editor(s)
Uwe Brahm
Christine Kiesel
Christine Kiesel
Christine Kiesel
Christine Kiesel
Edit Dates
07/07/2007 00:42:51
27.06.2007 16:31:31
27.06.2007 16:12:19
27.06.2007 08:41:58
03/20/2007 02:08:42 PM