MPI-INF D1 Publications: Journal Article: An improved algorithm for {Klee's} measure problem on fat boxes

Journal Article
@Article
Artikel in Fachzeitschrift

Show entries of:

this year (2023) | last year (2022) | two years ago (2021) | Notes URL

Action:

Options:

Library locked

Goto entry point

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:
(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

Edit History (please click the blue arrow to see the details)

	Editor(s) [Library]	Created 12/12/2012 17:47:25
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