ALBERT — All Library Books, journals and Electronic Records Telegrafenberg

Hits per page

hit 1 - 1 | 1 hit

Select All Export

Electronic Resource

The upper envelope of piecewise linear functions and the boundary of a region enclosed by convex plates: Combinatorial analysis (1989)

Pach, János ; Sharir, Micha

Springer

Discrete & computational geometry 4 (1989), S. 291-309

add to mindlist on the mindlist

Details

ISSN: 1432-0444

Source: Springer Online Journal Archives 1860-2000

Topics: Computer Science , Mathematics

Notes: Abstract Letf 1, ...,f m be (partially defined) piecewise linear functions ofd variables whose graphs consist ofn d-simplices altogether. We show that the maximal number ofd-faces comprising the upper envelope (i.e., the pointwise maximum) of these functions isO(n d α(n)), whereα(n) denotes the inverse of the Ackermann function, and that this bound is tight in the worst case. If, instead of the upper envelope, we consider any single connected componentC enclosed byn d-simplices (or, more generally, (d − 1)-dimensional compact convex sets) in ℝ d+1 , then we show that the overall combinatorial complexity of the boundary ofC is at mostO(n d+1−ɛ(d+1) ) for some fixed constantɛ(d+1)〉0.

Type of Medium: Electronic Resource

URL: http://dx.doi.org/10.1007/BF02187732

	Location	Call Number	Expected	Availability

Others were also interested in ...

Paper (German National Licenses)

Fulltext

hit 1 - 1 | 1 hit