New upper bounds in Klee's measure problem

Mark H. Overmars; Chee Keng Yap

doi:10.1137/0220065

New upper bounds in Klee's measure problem

Mark H. Overmars, Chee Keng Yap

Computer Science

Research output: Contribution to journal › Article › peer-review

Abstract

New upper bounds for the measure problem of Klee are given which significantly improve the previous bounds for dimensions greater than two. An O(n^d/2 log n, n) time-space upper bound is obtained and used to compute the measure of a set of n boxes in Euclidean d-space. The solution is based on new data structure, which is called an orthogonal partition tree. This structure has order applications as well.

Original language	English (US)
Pages (from-to)	1034-1045
Number of pages	12
Journal	SIAM Journal on Computing
Volume	20
Issue number	6
DOIs	https://doi.org/10.1137/0220065
State	Published - 1991

ASJC Scopus subject areas

General Computer Science
General Mathematics

Access to Document

10.1137/0220065

Cite this

@article{2235e7c8923c44d79f9fe607aa554ab9,

title = "New upper bounds in Klee's measure problem",

abstract = "New upper bounds for the measure problem of Klee are given which significantly improve the previous bounds for dimensions greater than two. An O(nd/2 log n, n) time-space upper bound is obtained and used to compute the measure of a set of n boxes in Euclidean d-space. The solution is based on new data structure, which is called an orthogonal partition tree. This structure has order applications as well.",

author = "Overmars, {Mark H.} and Yap, {Chee Keng}",

year = "1991",

doi = "10.1137/0220065",

language = "English (US)",

volume = "20",

pages = "1034--1045",

journal = "SIAM Journal on Computing",

issn = "0097-5397",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "6",

}

TY - JOUR

T1 - New upper bounds in Klee's measure problem

AU - Overmars, Mark H.

AU - Yap, Chee Keng

PY - 1991

Y1 - 1991

N2 - New upper bounds for the measure problem of Klee are given which significantly improve the previous bounds for dimensions greater than two. An O(nd/2 log n, n) time-space upper bound is obtained and used to compute the measure of a set of n boxes in Euclidean d-space. The solution is based on new data structure, which is called an orthogonal partition tree. This structure has order applications as well.

AB - New upper bounds for the measure problem of Klee are given which significantly improve the previous bounds for dimensions greater than two. An O(nd/2 log n, n) time-space upper bound is obtained and used to compute the measure of a set of n boxes in Euclidean d-space. The solution is based on new data structure, which is called an orthogonal partition tree. This structure has order applications as well.

UR - http://www.scopus.com/inward/record.url?scp=0026406169&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0026406169&partnerID=8YFLogxK

U2 - 10.1137/0220065

DO - 10.1137/0220065

M3 - Article

AN - SCOPUS:0026406169

SN - 0097-5397

VL - 20

SP - 1034

EP - 1045

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

IS - 6

ER -

New upper bounds in Klee's measure problem

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this