A role of lower semicontinuous functions in the combinatorial complexity of geometric problems

Jerzy W. Jaromczyk; Grzegorz Świştek

doi:10.1016/0885-064X(91)90004-H

A role of lower semicontinuous functions in the combinatorial complexity of geometric problems

Jerzy W. Jaromczyk, Grzegorz Świştek

Computer Science

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

Abstract

This paper studies an impact of geometric degeneracies on the complexity of geometric objects which are unions and intersections of open regions. We demonstrate a technique, based on the concept of lower semicontinuous functions, for proving that the maximum complexity is achieved on nondegenerate configurations of regions. We discuss in this context the complexity of stabbing regions, and arrangements of Jordan curves.

Original language	English
Pages (from-to)	174-183
Number of pages	10
Journal	Journal of Complexity
Volume	7
Issue number	2
DOIs	https://doi.org/10.1016/0885-064X(91)90004-H
State	Published - Jun 1991

Bibliographical note

Copyright:
Copyright 2014 Elsevier B.V., All rights reserved.

ASJC Scopus subject areas

Algebra and Number Theory
Statistics and Probability
Numerical Analysis
General Mathematics
Control and Optimization
Applied Mathematics

Access to Document

10.1016/0885-064X(91)90004-H

Cite this

@article{409c1e4173374dd6bacf156a0f55b4be,

title = "A role of lower semicontinuous functions in the combinatorial complexity of geometric problems",

abstract = "This paper studies an impact of geometric degeneracies on the complexity of geometric objects which are unions and intersections of open regions. We demonstrate a technique, based on the concept of lower semicontinuous functions, for proving that the maximum complexity is achieved on nondegenerate configurations of regions. We discuss in this context the complexity of stabbing regions, and arrangements of Jordan curves.",

author = "Jaromczyk, {Jerzy W.} and Grzegorz {\'S}wi{\c s}tek",

year = "1991",

month = jun,

doi = "10.1016/0885-064X(91)90004-H",

language = "English",

volume = "7",

pages = "174--183",

number = "2",

}

TY - JOUR

T1 - A role of lower semicontinuous functions in the combinatorial complexity of geometric problems

AU - Jaromczyk, Jerzy W.

AU - Świştek, Grzegorz

PY - 1991/6

Y1 - 1991/6

N2 - This paper studies an impact of geometric degeneracies on the complexity of geometric objects which are unions and intersections of open regions. We demonstrate a technique, based on the concept of lower semicontinuous functions, for proving that the maximum complexity is achieved on nondegenerate configurations of regions. We discuss in this context the complexity of stabbing regions, and arrangements of Jordan curves.

AB - This paper studies an impact of geometric degeneracies on the complexity of geometric objects which are unions and intersections of open regions. We demonstrate a technique, based on the concept of lower semicontinuous functions, for proving that the maximum complexity is achieved on nondegenerate configurations of regions. We discuss in this context the complexity of stabbing regions, and arrangements of Jordan curves.

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

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

U2 - 10.1016/0885-064X(91)90004-H

DO - 10.1016/0885-064X(91)90004-H

M3 - Article

AN - SCOPUS:44949280041

SN - 0885-064X

VL - 7

SP - 174

EP - 183

JO - Journal of Complexity

JF - Journal of Complexity

IS - 2

ER -

A role of lower semicontinuous functions in the combinatorial complexity of geometric problems

Abstract

Bibliographical note

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this