An acyclicity theorem for cell complexes in d dimensions
type: Item
instance of: scholarly article
title: An acyclicity theorem for cell complexes in d dimensions
zbMATH Open document ID: 0722.52004
DOI: 10.1007/BF02122779
author: Herbert Edelsbrunner
published in: Combinatorica
publication date: 1990-01-01T00:00:00Z
review text: In vielen, meist 3-dimensionalen Anwendungen spielt die davor/dahinter- Relation \(<\) zwischen konvexen Körpern eine wichtige Rolle, z.B. in der Computergraphik: Welcher Teil eines konvexen Körpers ist, von einem gewissen Gesichtspunkt aus, sichtbar, und welcher Teil ist von anderen Körpern verdeckt? Falls die Relation azyklisch ist, d.h. es keine Körperfolge \(s_ 1,s_ 2,...,s_ n\) so gibt, daß \(s_ 1<s_ 2<...<s_ n<s_ 1\) gilt, kennt man leistungsfähige Algorithmen zur Lösung solcher und ähnlicher Probleme; leider versagen sie, wenn die Relation Zykeln enthält. Der Autor zeigt, daß für gewisse Zellkomplexe im \(E^ d\) die davor/dahinter-Relation azyklisch ist. Das gilt z.B. für die Delaunay- Triangulation einer endlichen Punktmenge, allgemeiner für jeden regulären d-dimensionalen Zellkomplex, und auch für den Komplex seiner k-dimensionalen Seiten (k\(\leq d)\). Dabei heißt ein Zellkomplex regulär, wenn er die Projektion des Randes eines \((d+1)\)-dimensionalen konvexen Polytops ist.
Mathematics Subject Classification ID: 52A20
Mathematics Subject Classification ID: 52A30
Mathematics Subject Classification ID: 52C22
Mathematics Subject Classification ID: 05B45
Mathematics Subject Classification ID: 05B30
Mathematics Subject Classification ID: 68U05
zbMATH DE Number: 4190572
zbMATH Keywords: acyclic relation
zbMATH Keywords: visibility
zbMATH Keywords: cell-complex
zbMATH Keywords: in front of/behind-relation
zbMATH Keywords: Delaunay triangulation
zbMATH Keywords: regular d-dimensional cell complex
reviewed by: Jonathan Schaer
MaRDI profile type: Publication
cites work: Power Diagrams: Properties, Algorithms and Applications
cites work: How to search in history
cites work: Q4760292
cites work: Q3772828
cites work: On the shape of a set of points in the plane
cites work: On sorting triangles in a Delaunay tessellation
description: scientific article; zbMATH DE number 4190572