---
_id: '4001'
abstract:
- lang: eng
text: 'The construction of shape spaces is studied from a mathematical and a computational
viewpoint. A program is outlined reducing the problem to four tasks: the representation
of geometry, the canonical deformation of geometry, the measuring of distance
in shape space, and the selection of base shapes. The technical part of this paper
focuses on the second task: the specification of a deformation mixing two or more
shapes in continuously changing proportions. (C) 2001 Elsevier Science B.V All
rights reserved.'
acknowledgement: National Science Foundation under grants CCR-96-19542 and CCR-97-12088,
and by the Army Research Office under grant DAAG55-98-1-0177.
article_processing_charge: No
article_type: original
author:
- first_name: Ho
full_name: Cheng, Ho
last_name: Cheng
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Ping
full_name: Fu, Ping
last_name: Fu
citation:
ama: 'Cheng H, Edelsbrunner H, Fu P. Shape space from deformation. Computational
Geometry: Theory and Applications. 2001;19(2-3):191-204. doi:10.1016/S0925-7721(01)00021-9'
apa: 'Cheng, H., Edelsbrunner, H., & Fu, P. (2001). Shape space from deformation.
Computational Geometry: Theory and Applications. Elsevier. https://doi.org/10.1016/S0925-7721(01)00021-9'
chicago: 'Cheng, Ho, Herbert Edelsbrunner, and Ping Fu. “Shape Space from Deformation.”
Computational Geometry: Theory and Applications. Elsevier, 2001. https://doi.org/10.1016/S0925-7721(01)00021-9.'
ieee: 'H. Cheng, H. Edelsbrunner, and P. Fu, “Shape space from deformation,” Computational
Geometry: Theory and Applications, vol. 19, no. 2–3. Elsevier, pp. 191–204,
2001.'
ista: 'Cheng H, Edelsbrunner H, Fu P. 2001. Shape space from deformation. Computational
Geometry: Theory and Applications. 19(2–3), 191–204.'
mla: 'Cheng, Ho, et al. “Shape Space from Deformation.” Computational Geometry:
Theory and Applications, vol. 19, no. 2–3, Elsevier, 2001, pp. 191–204, doi:10.1016/S0925-7721(01)00021-9.'
short: 'H. Cheng, H. Edelsbrunner, P. Fu, Computational Geometry: Theory and Applications
19 (2001) 191–204.'
date_created: 2018-12-11T12:06:22Z
date_published: 2001-07-01T00:00:00Z
date_updated: 2023-05-10T12:57:14Z
day: '01'
doi: 10.1016/S0925-7721(01)00021-9
extern: '1'
intvolume: ' 19'
issue: 2-3
language:
- iso: eng
month: '07'
oa_version: None
page: 191 - 204
publication: 'Computational Geometry: Theory and Applications'
publication_identifier:
issn:
- 0925-7721
publication_status: published
publisher: Elsevier
publist_id: '2123'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Shape space from deformation
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 19
year: '2001'
...
---
_id: '4002'
abstract:
- lang: eng
text: Shape deformation refers to the continuous change of one geometric object
to another. We develop a software tool for planning, analyzing and visualizing
deformations between two shapes in R-2. The deformation is generated automatically
without any user intervention or specification of feature correspondences. A unique
property of the tool is the explicit availability of a two-dimensional shape space,
which can be used for designing the deformation either automatically by following
constraints and objectives or manually by drawing deformation paths.
acknowledgement: NSF under grants CCR-96-19542 and CCR-97-12088.
article_processing_charge: No
article_type: original
author:
- first_name: Siu
full_name: Cheng, Siu
last_name: Cheng
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Ping
full_name: Fu, Ping
last_name: Fu
- first_name: Ka
full_name: Lam, Ka
last_name: Lam
citation:
ama: 'Cheng S, Edelsbrunner H, Fu P, Lam K. Design and analysis of planar shape
deformation. Computational Geometry: Theory and Applications. 2001;19(2-3):205-218.
doi:10.1016/S0925-7721(01)00020-7'
apa: 'Cheng, S., Edelsbrunner, H., Fu, P., & Lam, K. (2001). Design and analysis
of planar shape deformation. Computational Geometry: Theory and Applications.
Elsevier. https://doi.org/10.1016/S0925-7721(01)00020-7'
chicago: 'Cheng, Siu, Herbert Edelsbrunner, Ping Fu, and Ka Lam. “Design and Analysis
of Planar Shape Deformation.” Computational Geometry: Theory and Applications.
Elsevier, 2001. https://doi.org/10.1016/S0925-7721(01)00020-7.'
ieee: 'S. Cheng, H. Edelsbrunner, P. Fu, and K. Lam, “Design and analysis of planar
shape deformation,” Computational Geometry: Theory and Applications, vol.
19, no. 2–3. Elsevier, pp. 205–218, 2001.'
ista: 'Cheng S, Edelsbrunner H, Fu P, Lam K. 2001. Design and analysis of planar
shape deformation. Computational Geometry: Theory and Applications. 19(2–3), 205–218.'
mla: 'Cheng, Siu, et al. “Design and Analysis of Planar Shape Deformation.” Computational
Geometry: Theory and Applications, vol. 19, no. 2–3, Elsevier, 2001, pp. 205–18,
doi:10.1016/S0925-7721(01)00020-7.'
short: 'S. Cheng, H. Edelsbrunner, P. Fu, K. Lam, Computational Geometry: Theory
and Applications 19 (2001) 205–218.'
date_created: 2018-12-11T12:06:22Z
date_published: 2001-07-01T00:00:00Z
date_updated: 2023-05-10T14:21:31Z
day: '01'
doi: 10.1016/S0925-7721(01)00020-7
extern: '1'
intvolume: ' 19'
issue: 2-3
language:
- iso: eng
month: '07'
oa_version: None
page: 205 - 218
publication: 'Computational Geometry: Theory and Applications'
publication_identifier:
issn:
- 0925-7721
publication_status: published
publisher: Elsevier
publist_id: '2124'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Design and analysis of planar shape deformation
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 19
year: '2001'
...
---
_id: '4018'
abstract:
- lang: eng
text: Given a subspace X subset of or equal to R-d and a finite set S subset of
or equal to R-d, we introduce the Delaunay complex, D-X, restricted by X. Its
simplices are spanned by subsets T subset of or equal to S for which the common
intersection of Voronoi cells meets X in a non-empty set. By the nerve theorem,
boolean OR D-X and X are homotopy equivalent if all such sets are contractible.
This paper proves a sufficient condition for boolean OR D-X and X be homeomorphic.
acknowledgement: Partially supported by the National Science Foundation, under grant
ASC-200301 and the Alan T. Waterman award, grant CCR-9118874.
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: Nimish
full_name: Shah, Nimish
last_name: Shah
citation:
ama: Edelsbrunner H, Shah N. Triangulating topological spaces. International
Journal of Computational Geometry & Applications. 1997;7(4):365-378. doi:10.1142/S0218195997000223
apa: Edelsbrunner, H., & Shah, N. (1997). Triangulating topological spaces.
International Journal of Computational Geometry & Applications. World
Scientific Publishing. https://doi.org/10.1142/S0218195997000223
chicago: Edelsbrunner, Herbert, and Nimish Shah. “Triangulating Topological Spaces.”
International Journal of Computational Geometry & Applications. World
Scientific Publishing, 1997. https://doi.org/10.1142/S0218195997000223.
ieee: H. Edelsbrunner and N. Shah, “Triangulating topological spaces,” International
Journal of Computational Geometry & Applications, vol. 7, no. 4. World
Scientific Publishing, pp. 365–378, 1997.
ista: Edelsbrunner H, Shah N. 1997. Triangulating topological spaces. International
Journal of Computational Geometry & Applications. 7(4), 365–378.
mla: Edelsbrunner, Herbert, and Nimish Shah. “Triangulating Topological Spaces.”
International Journal of Computational Geometry & Applications, vol.
7, no. 4, World Scientific Publishing, 1997, pp. 365–78, doi:10.1142/S0218195997000223.
short: H. Edelsbrunner, N. Shah, International Journal of Computational Geometry
& Applications 7 (1997) 365–378.
date_created: 2018-12-11T12:06:28Z
date_published: 1997-01-01T00:00:00Z
date_updated: 2022-08-19T08:32:23Z
day: '01'
doi: 10.1142/S0218195997000223
extern: '1'
intvolume: ' 7'
issue: '4'
language:
- iso: eng
month: '01'
oa_version: None
page: 365 - 378
publication: International Journal of Computational Geometry & Applications
publication_identifier:
issn:
- 0925-7721
publication_status: published
publisher: World Scientific Publishing
publist_id: '2106'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Triangulating topological spaces
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 7
year: '1997'
...
---
_id: '4021'
abstract:
- lang: eng
text: A homeomorphism from R-2 to itself distorts metric quantities, such as distance
and area. We describe an algorithm that constructs homeomorphisms with prescribed
area distortion. Such homeomorphisms can be used to generate cartograms, which
are geographic maps purposely distorted so their area distributions reflects a
variable different from area, as for example population density. The algorithm
generates the homeomorphism through a sequence of local piecewise linear homeomorphic
changes. Sample results produced by the preliminary implementation of the method
are included.
acknowledgement: 'The authors thank Jack Snoeyink for bringing the cartogram problem
to their attention, and Michael McAllister for providing pointers to the literature
on cartograms. '
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: Roman
full_name: Waupotitsch, Roman
last_name: Waupotitsch
citation:
ama: 'Edelsbrunner H, Waupotitsch R. A combinatorial approach to cartograms. Computational
Geometry: Theory and Applications. 1997;7(5-6):343-360. doi:10.1016/S0925-7721(96)00006-5'
apa: 'Edelsbrunner, H., & Waupotitsch, R. (1997). A combinatorial approach to
cartograms. Computational Geometry: Theory and Applications. Elsevier.
https://doi.org/10.1016/S0925-7721(96)00006-5'
chicago: 'Edelsbrunner, Herbert, and Roman Waupotitsch. “A Combinatorial Approach
to Cartograms.” Computational Geometry: Theory and Applications. Elsevier,
1997. https://doi.org/10.1016/S0925-7721(96)00006-5.'
ieee: 'H. Edelsbrunner and R. Waupotitsch, “A combinatorial approach to cartograms,”
Computational Geometry: Theory and Applications, vol. 7, no. 5–6. Elsevier,
pp. 343–360, 1997.'
ista: 'Edelsbrunner H, Waupotitsch R. 1997. A combinatorial approach to cartograms.
Computational Geometry: Theory and Applications. 7(5–6), 343–360.'
mla: 'Edelsbrunner, Herbert, and Roman Waupotitsch. “A Combinatorial Approach to
Cartograms.” Computational Geometry: Theory and Applications, vol. 7, no.
5–6, Elsevier, 1997, pp. 343–60, doi:10.1016/S0925-7721(96)00006-5.'
short: 'H. Edelsbrunner, R. Waupotitsch, Computational Geometry: Theory and Applications
7 (1997) 343–360.'
date_created: 2018-12-11T12:06:29Z
date_published: 1997-04-01T00:00:00Z
date_updated: 2022-08-19T08:12:03Z
day: '01'
doi: 10.1016/S0925-7721(96)00006-5
extern: '1'
intvolume: ' 7'
issue: 5-6
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://www.sciencedirect.com/science/article/pii/S0925772196000065
month: '04'
oa: 1
oa_version: Published Version
page: 343 - 360
popular_science: '1'
publication: 'Computational Geometry: Theory and Applications'
publication_identifier:
issn:
- 0925-7721
publication_status: published
publisher: Elsevier
publist_id: '2105'
status: public
title: A combinatorial approach to cartograms
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 7
year: '1997'
...
---
_id: '3581'
abstract:
- lang: eng
text: 'A number of rendering algorithms in computer graphics sort three-dimensional
objects by depth and assume that there is no cycle that makes the sorting impossible.
One way to resolve the problem caused by cycles is to cut the objects into smaller
pieces. In this paper we address the problem of estimating how many such cuts
arc always sufficient. We also consider a few related algorithmic and combinatorial
geometry problems. For example, we demonstrate that n lines in space can be sorted
in randomized expected time O(n4’st’), provided that they define no cycle. We
also prove an 0(n7’4) upper bound on the number of points in space so that there
are n lines with the property that for each point there are at least three noncoplanar
lines that contain it. '
acknowledgement: "* Bernard Chazelle wishes to acknowledge the National Science Foundation
for supporting this research in part under Grant CCR-9002352. Herbert Edelsbrunner
acknowledges the support of the National Science Foundation under grants CCR-8714565
and CCR-8921421. Richard Pollack was supported in part by NSF grant CCR-8901484,
NSA grant MDA904-89-H-2030, and DIMACS, a Science and Technology Center under NSF
grant STC88-09648. Raimund Seidel acknowledges support by NSF grant CCR-8809040.
Mich Sharir was partially supported by the Office of Naval\r\nResearch under Grant
N00014-87-K-0129, by the National Science Foundation under Grant CCR-89-01484, and
by grants from the U.S.-Israeli Binational Science Foundation and the Fund for Basic
Research administered by the Israeli Academy of Sciences."
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: Richard
full_name: Pollack, Richard
last_name: Pollack
- first_name: Raimund
full_name: Seidel, Raimund
last_name: Seidel
- first_name: Micha
full_name: Sharir, Micha
last_name: Sharir
- first_name: Jack
full_name: Snoeyink, Jack
last_name: Snoeyink
citation:
ama: 'Chazelle B, Edelsbrunner H, Guibas L, et al. Counting and cutting cycles of
lines and rods in space. Computational Geometry: Theory and Applications.
1992;1(6):305-323. doi:10.1016/0925-7721(92)90009-H'
apa: 'Chazelle, B., Edelsbrunner, H., Guibas, L., Pollack, R., Seidel, R., Sharir,
M., & Snoeyink, J. (1992). Counting and cutting cycles of lines and rods in
space. Computational Geometry: Theory and Applications. Elsevier. https://doi.org/10.1016/0925-7721(92)90009-H'
chicago: 'Chazelle, Bernard, Herbert Edelsbrunner, Leonidas Guibas, Richard Pollack,
Raimund Seidel, Micha Sharir, and Jack Snoeyink. “Counting and Cutting Cycles
of Lines and Rods in Space.” Computational Geometry: Theory and Applications.
Elsevier, 1992. https://doi.org/10.1016/0925-7721(92)90009-H.'
ieee: 'B. Chazelle et al., “Counting and cutting cycles of lines and rods
in space,” Computational Geometry: Theory and Applications, vol. 1, no.
6. Elsevier, pp. 305–323, 1992.'
ista: 'Chazelle B, Edelsbrunner H, Guibas L, Pollack R, Seidel R, Sharir M, Snoeyink
J. 1992. Counting and cutting cycles of lines and rods in space. Computational
Geometry: Theory and Applications. 1(6), 305–323.'
mla: 'Chazelle, Bernard, et al. “Counting and Cutting Cycles of Lines and Rods in
Space.” Computational Geometry: Theory and Applications, vol. 1, no. 6,
Elsevier, 1992, pp. 305–23, doi:10.1016/0925-7721(92)90009-H.'
short: 'B. Chazelle, H. Edelsbrunner, L. Guibas, R. Pollack, R. Seidel, M. Sharir,
J. Snoeyink, Computational Geometry: Theory and Applications 1 (1992) 305–323.'
date_created: 2018-12-11T12:04:04Z
date_published: 1992-06-01T00:00:00Z
date_updated: 2022-03-16T10:41:58Z
day: '01'
doi: 10.1016/0925-7721(92)90009-H
extern: '1'
intvolume: ' 1'
issue: '6'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://www.sciencedirect.com/science/article/pii/092577219290009H?via%3Dihub
month: '06'
oa: 1
oa_version: Published Version
page: 305 - 323
publication: 'Computational Geometry: Theory and Applications'
publication_identifier:
issn:
- 0925-7721
publication_status: published
publisher: Elsevier
publist_id: '2804'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Counting and cutting cycles of lines and rods in space
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 1
year: '1992'
...