---
_id: '4052'
abstract:
- lang: eng
text: This paper describes an effective procedure for stratifying a real semi-algebraic
set into cells of constant description size. The attractive feature of our method
is that the number of cells produced is singly exponential in the number of input
variables. This compares favorably with the doubly exponential size of Collins'
decomposition. Unlike Collins' construction, however, our scheme does not produce
a cell complex but only a smooth stratification. Nevertheless, we are able to
apply our results in interesting ways to problems of point location and geometric
optimization.
acknowledgement: The authors wish to thank DEC/Systems Research Center and DEC/Paris
Research Laboratory, where part of this research was conducted. For individual support,
Bernard Chazelle acknowledges the National Science Foundation for supporting this
research in part under Grant CCR-8700917. Herbert Edelsbrunner acknowledges the
support of the National Science Foundation under Grant CCR-8714565. Micha Sharir
acknowledges the Office of Naval Research under Grant N00014-87-K-0129, the National
Science Foundation under Grant No. NSF-DCR-83-20085, grants from the Digital Equipment
Corporation and the IBM Corporation, and a research grant from the US-Israeli Binational
Science Foundation.
article_processing_charge: No
article_type: original
author:
- first_name: Bernard
full_name: Chazelle, Bernard
last_name: Chazelle
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Leonidas
full_name: Guibas, Leonidas
last_name: Guibas
- first_name: Micha
full_name: Sharir, Micha
last_name: Sharir
citation:
ama: Chazelle B, Edelsbrunner H, Guibas L, Sharir M. A singly exponential stratification
scheme for real semi-algebraic varieties and its applications. Theoretical
Computer Science. 1991;84(1):77-105. doi:10.1016/0304-3975(91)90261-Y
apa: Chazelle, B., Edelsbrunner, H., Guibas, L., & Sharir, M. (1991). A singly
exponential stratification scheme for real semi-algebraic varieties and its applications.
Theoretical Computer Science. Elsevier. https://doi.org/10.1016/0304-3975(91)90261-Y
chicago: Chazelle, Bernard, Herbert Edelsbrunner, Leonidas Guibas, and Micha Sharir.
“A Singly Exponential Stratification Scheme for Real Semi-Algebraic Varieties
and Its Applications.” Theoretical Computer Science. Elsevier, 1991. https://doi.org/10.1016/0304-3975(91)90261-Y.
ieee: B. Chazelle, H. Edelsbrunner, L. Guibas, and M. Sharir, “A singly exponential
stratification scheme for real semi-algebraic varieties and its applications,”
Theoretical Computer Science, vol. 84, no. 1. Elsevier, pp. 77–105, 1991.
ista: Chazelle B, Edelsbrunner H, Guibas L, Sharir M. 1991. A singly exponential
stratification scheme for real semi-algebraic varieties and its applications.
Theoretical Computer Science. 84(1), 77–105.
mla: Chazelle, Bernard, et al. “A Singly Exponential Stratification Scheme for Real
Semi-Algebraic Varieties and Its Applications.” Theoretical Computer Science,
vol. 84, no. 1, Elsevier, 1991, pp. 77–105, doi:10.1016/0304-3975(91)90261-Y.
short: B. Chazelle, H. Edelsbrunner, L. Guibas, M. Sharir, Theoretical Computer
Science 84 (1991) 77–105.
date_created: 2018-12-11T12:06:39Z
date_published: 1991-07-22T00:00:00Z
date_updated: 2022-03-02T10:23:58Z
day: '22'
doi: 10.1016/0304-3975(91)90261-Y
extern: '1'
intvolume: ' 84'
issue: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://www.sciencedirect.com/science/article/pii/030439759190261Y?via%3Dihub
month: '07'
oa: 1
oa_version: Published Version
page: 77 - 105
publication: Theoretical Computer Science
publication_identifier:
eissn:
- 1879-2294
issn:
- 0304-3975
publication_status: published
publisher: Elsevier
publist_id: '2073'
quality_controlled: '1'
scopus_import: '1'
status: public
title: A singly exponential stratification scheme for real semi-algebraic varieties
and its applications
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 84
year: '1991'
...
---
_id: '4084'
abstract:
- lang: eng
text: "A tour of a finite set P of points is a necklace-tour if there are disks
with the points in P as centers such that two disks intersect if and only if their
centers are adjacent in . It has been observed by Sanders that a necklace-tour
is an optimal traveling salesman tour.\r\n\r\nIn this paper, we present an algorithm
that either reports that no necklace-tour exists or outputs a necklace-tour of
a given set of n points in O(n2 log n) time. If a tour is given, then we can test
in O(n2) time whether or not this tour is a necklace-tour. Both algorithms can
be generalized to ƒ-factors of point sets in the plane. The complexity results
rely on a combinatorial analysis of certain intersection graphs of disks defined
for finite sets of points in the plane."
article_processing_charge: No
article_type: original
author:
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Günter
full_name: Rote, Günter
last_name: Rote
- first_name: Emo
full_name: Welzl, Emo
last_name: Welzl
citation:
ama: Edelsbrunner H, Rote G, Welzl E. Testing the necklace condition for shortest
tours and optimal factors in the plane. Theoretical Computer Science. 1989;66(2):157-180.
doi:10.1016/0304-3975(89)90133-3
apa: Edelsbrunner, H., Rote, G., & Welzl, E. (1989). Testing the necklace condition
for shortest tours and optimal factors in the plane. Theoretical Computer Science.
Elsevier. https://doi.org/10.1016/0304-3975(89)90133-3
chicago: Edelsbrunner, Herbert, Günter Rote, and Emo Welzl. “Testing the Necklace
Condition for Shortest Tours and Optimal Factors in the Plane.” Theoretical
Computer Science. Elsevier, 1989. https://doi.org/10.1016/0304-3975(89)90133-3.
ieee: H. Edelsbrunner, G. Rote, and E. Welzl, “Testing the necklace condition for
shortest tours and optimal factors in the plane,” Theoretical Computer Science,
vol. 66, no. 2. Elsevier, pp. 157–180, 1989.
ista: Edelsbrunner H, Rote G, Welzl E. 1989. Testing the necklace condition for
shortest tours and optimal factors in the plane. Theoretical Computer Science.
66(2), 157–180.
mla: Edelsbrunner, Herbert, et al. “Testing the Necklace Condition for Shortest
Tours and Optimal Factors in the Plane.” Theoretical Computer Science,
vol. 66, no. 2, Elsevier, 1989, pp. 157–80, doi:10.1016/0304-3975(89)90133-3.
short: H. Edelsbrunner, G. Rote, E. Welzl, Theoretical Computer Science 66 (1989)
157–180.
date_created: 2018-12-11T12:06:51Z
date_published: 1989-08-01T00:00:00Z
date_updated: 2022-02-11T11:15:43Z
day: '01'
doi: 10.1016/0304-3975(89)90133-3
extern: '1'
intvolume: ' 66'
issue: '2'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://www.sciencedirect.com/science/article/pii/0304397589901333?via%3Dihub
month: '08'
oa: 1
oa_version: Published Version
page: 157 - 180
publication: Theoretical Computer Science
publication_identifier:
eissn:
- 1879-2294
issn:
- 0304-3975
publication_status: published
publisher: Elsevier
publist_id: '2041'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Testing the necklace condition for shortest tours and optimal factors in the
plane
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 66
year: '1989'
...