For the cake-cutting problem, Alijani, et al. [Reza Alijani et al., 2017; Masoud Seddighin et al., 2019] and Asano and Umeda [Takao Asano and Hiroyuki Umeda, 2020; Takao Asano and Hiroyuki Umeda, 2020] gave envy-free and truthful mechanisms with a small number of cuts, where the desired part of each player’s valuation function is a single interval on a given cake. In this paper, we give envy-free and truthful mechanisms with a small number of cuts, which are much simpler than those proposed by Alijani, et al. [Reza Alijani et al., 2017; Masoud Seddighin et al., 2019] and Asano and Umeda [Takao Asano and Hiroyuki Umeda, 2020; Takao Asano and Hiroyuki Umeda, 2020]. Furthermore, we show that this approach can be applied to the envy-free and truthful mechanism proposed by Chen, et al. [Yiling Chen et al., 2013], where the valuation function of each player is more general and piecewise uniform. Thus, we can obtain an envy-free and truthful mechanism with a small number of cuts even if the valuation function of each player is piecewise uniform, which solves the future problem posed by Alijani, et al. [Reza Alijani et al., 2017; Masoud Seddighin et al., 2019].

The mechanism for the cake-cutting problem based on the expansion process with unlocking proposed by Alijani, Farhadi, Ghodsi, Seddighin, and Tajik [Reza Alijani et al., 2017; Masoud Seddighin et al., 2019] uses a small number of cuts, but is not actually envy-free and truthful, although they claimed that it is envy-free and truthful. In this paper, we consider the same cake-cutting problem and give a new envy-free and truthful mechanism with a small number of cuts, which is not based on their expansion process with unlocking.

A pair of nonnegative integer sequences {D1, D2} with D1 = (d1,1, d1,2, …, dnD2= (d2,1, d2,2, …, dna bipartite graphical sequence, if there is a bipartite graph G with degrees{D1, D2} (i.e., G has two independent vertex sets V1 = {v1,1, v1,2, …, vnV2 = {v2,1, v2,2, …, vnsuch that di,ji the degree of vertex vi,jiG for each i = 1, 2 and ji = 1, 2, …, ni). In other words,{D1, D2} is a bipartite graphical sequence if and only if there is an n1× n2 matrix of 0's and 1's havingdjj1 and djj2. The connectivity κ({D1, D2}) of a bipartite graphical sequence{D1, D2} is defined to be the maximum integer k such that there is a k-connected bipartite graph with degrees {D1, D2}. In this paper, we present a characterization of a k-connected bipartite graphical sequence and an O(n log log n) time algorithm, for a given bipartite graphical sequence {D1, D2}, to construct a κ({D1, D2})-connected bipartite graph with degrees {D1, D2} (n = n1+n2). © 1997 John Wiley & Sons, Inc.

The author presents an efficient algorithm for finding a route interconnecting two terminals of arbitrary polygonal shape in two layers. The main feature of the router to be distinguished from the existing grid-free routers is that it can handle large vias. The author has also considered the extension to multi-terminal nets and demonstrate a native algorithm which repeats the same path finding process for each constituent terminal. Careful considerations may lead to a more efficient way such that three regions (horizontal and vertical routable regions and via acceptable region) are not reconstructed each time but updated only around the path obtained. In order to do that a data structure has been devised which can implement insertions and deletions of line segments each in O(log n) time. Based on the proposed algorithm it is possible to solve a practical problem which is concerned with a layout design of bipolar LSIs. In this case the purpose is to find an orthogonal wiring route of predetermined width between pairs of terminals avoiding polygonal obstacles in two layers.>

The orthogonal segment intersection search problem is stated as follows: Given a set S of n orthogonal segments in the plane, report all the segments of S that intersect a given orthogonal query segment. For this problem, we propose a simple and practical algorithm based on bucketing techniques. It constructs, in Ο(n) time preprocessing, a search structure of size Ο(n) so that all the segments of S intersecting a query segment can be reported in Ο(k) time in the average case, where k is the number of the reported segments. The proposed algorithm as well as existing algorithms is implemented in FORTRAN, and their practical efficiencies are investigated through computational experiments. It is shown that our Ο(k) search time, Ο(n) space and Ο(n) preprocessing time algorithm is practically the most efficient among the tested algorithms.

For a property $\pi $ on graphs, the corresponding edge-deletion problem $P_{{\text{ED}}} (\pi )$ (on planar graphs) is stated as follows: given a (planar) graph G, find a set of edges of minimum cardinality whose deletion results in a graph satisfying $\pi $. We show that the edge-deletion problem $P_{{\text{ED}}} (\pi )$ on planar graphs is NP-hard if $\pi $ is nontrivial and is determined by the weighted 3-connected components. As a corollary, the edge-deletion problem $P_{{\text{ED}}} (\pi )$ on planar graphs is NP-complete for several properties $\pi $, such as $\pi = $ “series-parallel,” “outerplanar,” “without cocycles of cardinality $ \geqq 3$,” etc.

The problem of partitioning a polygonal region into a minimum number of trapezoids with two horizontal sides is discussed. A triangle with a horizontal side is considered to be a trapezoid with two horizontal sides one of which is degenerate. First, a method of achieving a minimum partition is presented. The number M * of the trapezoids in the minimum partition of a polygonal region P is shown to be M * = n + w - h - d - 1, where n , w , and h are the number of vertices, windows (holes), and horizontal edges of P , respectively, and d is the cardinality of a maximum independent set of the straight-lines-in-the-plane graph associated with P . Next, this problem is shown to be polynomially equivalent to the problem of finding a maximum independent set of a straight-lines-in-the-plane graph, and consequently, it is shown to be NP-complete. However, for a polygonal region without windows, an O ( n 2 )-time algorithm for partitioning it into a minimum number of trapezoids is presented. Finally, an O ( n log n )-time approximation algorithm with the performance bound 3 is presented.

In this paper, we show that many graph search problems can be solved quite efficiently for a geometric intersection graph of horizontal and vertical line segments. We first extract several basic operations for depth first search and breadth first search on a graph. Then we present data structures for the intersection graph in terms of which those operations can be implemented in an efficient manner. The data structures enable us to solve various graph search problems besides depth first search and breadth first search. Specifying the results obtained in this paper for an intersection graph of n horizontal and vertical segments with m pairs of intersecting segments, we obtain algorithms with the following complexity, where $N = \min \{ m,n\log n\} $. (i) Depth first search and breadth first search can be executed in $O(n\log n)$ time and $O(N)$ space. (ii) The biconnected components can be found in $O(n\log n)$ time and $O(N)$ space. (iii) A maximum matching and a maximum independent set can be found in $O(\sqrt n N)$ time and $O(N)$ space when no two horizontal (vertical) segments intersect. (iv) The connectivity $k_G $ can be found in $O(k_G n^{{3 / 2}} N)$ time and $O(N)$ space. Our algorithms can be applied to various practical problems such as the problem of finding a minimum dissection of a rectilinear region, which arises in the manipulation of VLSI artwork data, and the problem of determining whether there is a Manhattan wiring on a single layer, which arises in the design automation of digital systems.

Consider a collection of disjoint polygons in the plane containing a total of n edges. We show how to build, in O(n2) time and space, a data structure from which in O(n) time we can compute the visibility polygon of a given point with respect to the polygon collection. As an application of this structure, the visibility graph of the given polygons can be constructed in O(n2) time and space. This implies that the shortest path that connects two points in the plane and avoids the polygons in our collection can be computed in O(n2) time, improving earlier O(n2 log n) results.

In this paper, we consider two restricted types of dynamic orthogonal segment intersection search problems. One is the problem in which the underlying set is updated only by insertions. In the other, the set is updated only by deletions. We show that an intermixed sequence of O(n) queries and updates in both problems can be executed on-line in O(n log n+K) time and O(n log n) space, where K is the total number of reported intersections. Our algorithms utilize set-union and set-splitting algorithms. Especially, we present a linear-time algorithm for the incremental set-splitting problem, and use it for the problem in which only insertions are allowed. The data structures developed here give new better solutions for various geometric problems on orthogonal segments. We give a paradigm of solving those geometric problems by combining graph algorithms with these data structures, and describe a variety of applications.

article Free Access Share on A new point-location algorithm and its practical efficiency: comparison with existing algorithms Author: Ta. Asano Department of Mathematical Engineering and Instrumentation Physics, Faculty of Engineering, University of Tokyo, Bunkyo-ku, Tokyo, Japan 113 Department of Mathematical Engineering and Instrumentation Physics, Faculty of Engineering, University of Tokyo, Bunkyo-ku, Tokyo, Japan 113View Profile Authors Info & Claims ACM Transactions on GraphicsVolume 3Issue 2April 1984 pp 86–109https://doi.org/10.1145/357337.357338Published:01 April 1984Publication History 52citation921DownloadsMetricsTotal Citations52Total Downloads921Last 12 Months43Last 6 weeks13 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

We consider the problem of partitioning a polygonal region into a minimum number of trapezoids with two horizontal sides. Triangles with a horizontal side are considered to be trapezoids with two horizontal sides one of which is degenerate. In this paper we show that this problem is equivalent to the problem of finding a maximum independent set of a straight-lines-in-the-plane graph. Thus it is shown to be NP-complete. Next we present an O(n log n) natural approximation algorithm which uses only horizontal chords to partition a polygonal region P into trapezoids, where n is the number of vertices of P. We show that the absolute performance ratio of the algorithm is three. We can also design another approximation algorithm with the ratio (1 + 2/c) if we have a (1 - 1/c) approximation algorithm for the maximum independent set problem on straight-lines-in-the-plane graphs, where c is some constant. Finally, we give an O(n3) exact algorithm for polygonal regions without windows.

For a property π on graphs, the corresponding edge-deletion problem PED(π) (edge-contraction problem PEC(π), resp.) is defined as follows: Given a graph G, find a set of edges of minimum cardinality whose deletion (contraction, resp.) results in a graph satisfying property π. In this paper we show that the edge-deletion problem PED (π) (edge-contraction problem PEC (π), resp.) is NP-hard if π is hereditary on subgraphs (contractions, resp.) and is determined by the 3-connected components.

A tour in a sequential machine is a shortest input sequence taking the machine from some initial state, through all of its remaining states and back again into its initial state. A. K. Dewdney and A. L. Szilard [2] found the best upper bound for tour length for two classes of machines: the class of n-state sequential machines with unrestricted input alphabet and the class of n-state sequential machines with a two-letter input alphabet. We define a strong circulation on a strong digraph D whose volume is equal to the tour length of D. Characterizing the volume of strong circulation, we derive the best upper bound for tour length for n-state sequential machines with an r-letter input alphabet. Putting $r = 2$ or $r = \infty $, we have the same results as those obtained by A. K. Dewdney and A. L. Szilard.