Journal Article
@Article
Artikel in Fachzeitschrift


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:




Library Locked Library locked




Author, Editor(s)

Author(s):

Bringmann, Karl

dblp



BibTeX cite key*:

BringmannCGTA12

Title

Title*:

An improved algorithm for Klee's measure problem on fat boxes

Journal

Journal Title*:

Computational Geometry: Theory and Applications

Journal's URL:

http://www.journals.elsevier.com/computational-geometry/

Download URL
for the article:

http://dx.doi.org/10.1016/j.comgeo.2011.12.001

Language:

English

Publisher

Publisher's
Name:

Elsevier

Publisher's URL:

http://www.elsevier.com/

Publisher's
Address:

Amsterdam

ISSN:

0925-7721

Vol, No, pp, Date

Volume*:

45

Number:

5-6

Publishing Date:

July 2012

Pages*:

225-233

Number of
VG Pages:

9

Page Start:

225

Page End:

233

Sequence Number:


DOI:

10.1016/j.comgeo.2011.12.001

Note, Abstract, ©

Note:


(LaTeX) Abstract:

The measure problem of Klee asks for the volume of the union of n axis-parallel boxes in a fixed dimension d. We give an O(n^((d+2)/3)) time algorithm for the special case of all boxes being cubes or, more generally, fat boxes. Previously, the fastest run-time was n^(d/2) 2^O(log⁎n) , achieved by the general case algorithm of Chan [SoCG 2008]. For the general problem our run-time would imply a breakthrough for the k-clique problem.

URL for the Abstract:


Categories,
Keywords:

Geometric Data Structures, Union of Cubes

HyperLinks / References / URLs:

http://www.sciencedirect.com/science/article/pii/S0925772111000952

Copyright Message:


Personal Comments:


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:

@ARTICLE{BringmannCGTA12,
AUTHOR = {Bringmann, Karl},
TITLE = {An improved algorithm for {Klee's} measure problem on fat boxes},
JOURNAL = {Computational Geometry: Theory and Applications},
PUBLISHER = {Elsevier},
YEAR = {2012},
NUMBER = {5-6},
VOLUME = {45},
PAGES = {225--233},
ADDRESS = {Amsterdam},
MONTH = {July},
ISBN = {0925-7721},
DOI = {10.1016/j.comgeo.2011.12.001},
}


Entry last modified by Uwe Brahm, 02/06/2013
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
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)
[Library]
Created
12/12/2012 05:47:25 PM
Revisions
2.
1.
0.

Editor(s)
Uwe Brahm
Anja Becker
Karl Bringmann

Edit Dates
02/01/2013 02:07:48 PM
29.01.2013 12:40:13
12.12.2012 17:47:25